优先队列和堆
堆
堆是一颗具有特定性质的二叉树，基本要求是所有结点的值必须大于或等于（或者小于或等于）其孩子节点的值，另外树的高度h大于0，所有结点都处于第h或h-1层时，即堆也是一颗完全二叉树。
- 最大堆：结点的值必须大于或等于其孩子节点的值
- 最小堆：节点的值必须小于或等于其孩子节点的值
二叉堆
每个结点最多有两个孩子节点。
储存格式，由于堆在形式上是一颗完全二叉树，因此可以采用数组形式存储它。
以最大堆举例：
public class Heap {
public int[] array;
public int count;//元素个数
public int capacity;//堆的容量
public int heap_type;//最大堆还是最小堆
public Head(int capacity, int head_type);
//...
}
创建堆
public Heap(int capacity, int heap_type) {
this.heap_type = heap_type;
this.count = count;
this.capacity = capacity;
this.array = new int[capacity];
}
节点的双亲
由于二叉堆是一颗完全二叉树，因此对于i位置上的节点其父节点的位置在(i-1)/2。
public int Parent(int i) {
if(i <= 0 || i >= this.count) return -1;
return (i-1)/2;
}
节点的孩子
同上，子节点的位置为2*i+1和2*i+2
public int LeftChild(int i) {
int left = 2*i + 1;
if(left >= this.count) return -1;
return left;
}
public int RightChild(int i) {
inr right = 2*i +2;
if(right >= this.count) return -1;
return right;
}
获取堆中最大元素
最大堆的最大值即为根节点的值
public int GetMaximum() {
if(this.count == 0) return -1;
return this.array[0];
}
堆化元素
将i位置移动到堆中合适的位置，自上而下，称之为堆化，或者说向下渗透。
public void PercolateDown(int i) {
int l, r, max, temp;
l = LeftChild(i);
r = RightChild(i);
//对位置i的元素进行堆化，移到它合适的位置
if(l != -1 && this.array[l]>this.array[i]) max = l;
else max = i;//当前节点比其左节点大
if(r != -1 && this.array[r] > this.array[max]) max = r;
if(max!=i) {//交换位置
temp = this.array[i];
this.array[i] = this.array[max];
this.array[max] = temp;
}
//继续堆化
PercolateDown(max);
}
删除元素
二叉堆删除只能从根节点删除元素，这是标准堆支持的唯一操作，删除根节点后，再将最后一个元素移动到根节点， 然后对根节点进行堆化。
public int DeleteMax() {
if(this.count == 0) return -1;
int data = this.array[0];
this.array[0] = this.array[this.count - 1];
this.count--;//这里并没有删除最后一个元素，而是将最后一个元素复制到根节点，再将下标前移
PercolateDown(0);
return data;//返回删除的最大值
}
插入元素
从下往上堆化元素，称之为向上渗透
public int Insert(int data) {
int i;
if(this.count == this.capacity) {
ResizeHeap();//扩容
}
this.count++;
i = this.count - 1;
while(i >= 0 && data > this.array[(i-1)/2]) {
//跟父节点比较
this.array[i] = this.array[(i-1)/2];
i = (i-1)/2;
}
this.array[i] = data;
}
public void resizeHeap() {
int array_old = new int[this.capacity];
System.arraycopy(this.array, 0, array_old, this.count-1);
this.array = new int[this.capacity*2];
if(this.array == null) {
System.out.println("Memory Error");
return;
}
for(int i = 0; i<this.capacity; i++) {
this.array[i] = array_old[i];
this.capacity *= 2;
array_old = null;
}
}
