优先队列是一种抽象的数据类型，表示一组值和对这些值的操作，其中最重要的操作就是删除最大元素和插入元素。
二叉堆数组中，每个元素都要保证大于等于另两个特定位置的元素，相应这些位置的元素又至少要大于等于数组中的另两个的元素。
如果将所有元素弄成一个二叉树，灵魂画手就觉得此事很简单：
二叉树.png
这是一个二叉树，其中当它每一个节点都大于等于它的两个子节点时，称之为堆有序。
比如C D一定小于B B，E一定小于A。但E和B的大小比较不一定，可能E比D还小也说不定。唯一可确定的是，树的根节点，A一定是最大的元素。
二叉堆表示法：
如果我们用指针来表示堆有序的二叉树，那么每个元素都需要三个指针来找到它的上下结点，虽然可能不会全用上。如果我们采用完全二叉树complete tree
（完全二叉树从根结点到倒数第二层满足完美二叉树（完美就是都是有两个子结点，而且高度填充一样），最后一层可以不完全填充，其叶子结点都靠左对齐。）
甚至可以用数组直接表达，具体是层级表示，比如根节点在序号1，子节点则在序号2和3，以此类推（并不用序号0）
二叉堆就是一组堆有序的完全二叉树排序的元素，在数组中按照层次存储。一棵大小为N的完全二叉树的高度为log2N下取整（只有一个父结点高度认为为0）
这些元素在数组中用层次存储是有规律的，二叉堆中，位置k的结点的父结点的位置在（k/2下取整），它的两个子结点的位置为2k和2k+1。
上浮实现堆有序化
如果堆有序状态因为某个结点变得比它的父结点更大而被打破，这样就要不断交换它和它的父结点来修复有序状态。这种就好像是小弟立了功就被人提拔上去的感觉。
private void swim(int k){
while(k>1&&(k/2)<k){
exchange(a,k,k/2);
k=k/2;
}
}
下沉实现堆有序化
父结点比子结点的数小，所以父结点要和它的子结点交换，直到它没有子结点或者比子结点大为止。差不多就是上司犯错然后被降级的感觉
private void sink(int k) {
while(2*k<=n) {
int j=2*k;
if(j<n&&a[j]<a[j+1])j++; //找到两个子结点中较大的那个
if(a[k]>=a[j])break;
exchange(k, j);
k=j;
}
}
根据上面的sink和swim就可以实现对一个堆有序序列进行元素的增删，并维护它的顺序
public class MaxPQ {
private int n=0;
private int[] a;
public MaxPQ(int maxlength) {
a=new int[maxlength];
}
public int size() {
return n;
}
public void insert(int v) {
a[++n]=v;
swim(n);
}
public int delmax() { //这个很帅，将最大的拿出来让最底层的结点放上面来然后下沉排序
int max=a[1];
exchange(1, n--);
sink(1);
return max;
}
private void swim(int k){
while(k>1&&(k/2)<k){
exchange(k,k/2);
k=k/2;
}
}
private void sink(int k) {
while(2*k<=n) {
int j=2*k;
if(j<n&&a[j]<a[j+1])j++;
if(a[k]>=a[j])break;
exchange(k, j);
k=j;
}
}
private void exchange(int i,int j) {
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
对于这个有几点改进
- 这个可以用不定容数组代替定容数组
- 可以通过模拟多叉树来实现多叉堆，比如三叉堆就是位置k的元素有3k-1、3k、3k+1三个结点。同理修改d叉树也不是什么难事，我们需要在树高和d个子结点找到折中。
- 添加索引，方便从大到小遍历元素
堆排序
堆排序分成两个阶段，构造堆和下沉排序阶段。
堆的构造分成两种：一个是通过数组的从左往右遍历数组调用swim，一种是从右往左遍历数组调用sink方法。听说好像后面那种更加聪明。
有一种堆排序的实现方式如下，开始时扫描数组一半的元素用sink方法，因为我们可以跳过大小为一的子堆，因为n/2-n这些元素都是没有子结点的结点。
这里sink方法改了一下方法参数，但内容是一样的
public static void sort(int [] a){
int n=a.length();
for(int k=n/2;k>=1;k--){
sink(a,k,n);
}
//上面方法结束后保证堆有序了
//下沉排序
while(n>1){
exch(a,1,n--); //交换位置且缩小堆
sink(a,1,n);
}
}
下沉排序主要工作是在第二阶段完成的。这里我们将堆中最大元素删了，放在缩小堆后空出来的位置（其实是交换了元素位置再缩小堆）。然后再sink
堆排序是唯一一个能同时最优利用时间和空间的排序。在最坏的情况下也能保证2Nlogn的比较和恒定额外的空间。但是它很少利用缓存（啥意思？）
网友评论