当前位置: 技术问答>java相关
谁能讲讲堆数据结构(Heap)是怎么回事?
来源: 互联网 发布时间:2015-04-26
本文导语: 因为不明白Heap,所以以下代码有些看不明白。 请指教 谢谢! 附Java代码: public class Heap { private Comparable[] heap; private int size; private int capacity; private int capacityIncrement; /** * Construct a heap wit...
因为不明白Heap,所以以下代码有些看不明白。
请指教
谢谢!
附Java代码:
public class Heap
{
private Comparable[] heap;
private int size;
private int capacity;
private int capacityIncrement;
/**
* Construct a heap with initial capacity 10
* and capacity increment 0
*
* @since 1.0
* */
public Heap()
{
this(10, 0);
}
/**
* Construct a heap with initial capacity c
* and capacity increment 0
*
* @param c initial capacity for heap
* @exception IllegalArgumentException c is negative
* @since 1.0
* */
public Heap(int c)
{
this(c, 0);
}
/**
* Construct a heap with initial capacity c
* and capacity increment ci
*
* @param c initial capacity for heap
* @param ci capacity increment for heap
* @exception IllegalArgumentException c or ci is negative
* @since 1.0
* */
public Heap(int c, int ci)
{
if (c A.length)
throw new IllegalArgumentException();
int child = pos;
int parent = child / 2;
Comparable value = A[child];
while (parent > 0)
{
if (A[parent].compareTo(value) A.length
* @since 1.0
* */
private static void siftDown(Comparable[] A, int size, int pos)
{
if (pos size || size > A.length)
throw new IllegalArgumentException();
int parent = pos;
int child = 2 * parent;
Comparable value = A[parent];
while (child A.length)
throw new IllegalArgumentException();
for (int i = size / 2; i > 0; i--)
siftDown(A, size, i);
}
}
请指教
谢谢!
附Java代码:
public class Heap
{
private Comparable[] heap;
private int size;
private int capacity;
private int capacityIncrement;
/**
* Construct a heap with initial capacity 10
* and capacity increment 0
*
* @since 1.0
* */
public Heap()
{
this(10, 0);
}
/**
* Construct a heap with initial capacity c
* and capacity increment 0
*
* @param c initial capacity for heap
* @exception IllegalArgumentException c is negative
* @since 1.0
* */
public Heap(int c)
{
this(c, 0);
}
/**
* Construct a heap with initial capacity c
* and capacity increment ci
*
* @param c initial capacity for heap
* @param ci capacity increment for heap
* @exception IllegalArgumentException c or ci is negative
* @since 1.0
* */
public Heap(int c, int ci)
{
if (c A.length)
throw new IllegalArgumentException();
int child = pos;
int parent = child / 2;
Comparable value = A[child];
while (parent > 0)
{
if (A[parent].compareTo(value) A.length
* @since 1.0
* */
private static void siftDown(Comparable[] A, int size, int pos)
{
if (pos size || size > A.length)
throw new IllegalArgumentException();
int parent = pos;
int child = 2 * parent;
Comparable value = A[parent];
while (child A.length)
throw new IllegalArgumentException();
for (int i = size / 2; i > 0; i--)
siftDown(A, size, i);
}
}
|
堆就是一棵比较特殊的二叉树,对于最小堆(min Heap)他的每个节点的值都小于其孩子的值,最大堆相反。主要是用来做排序比较高效。
具体可以看数据结构的书。
具体可以看数据结构的书。