HeapSort
转载自：链接：https://www.jianshu.com/p/719b0de606a7 作者：Geek5Nan
侵删
主要内容概述
什么是二叉堆
-
二叉堆的有序化
当子节点 > 父节点
当父节点 > 子节点
二叉堆实现优先队列(priority queue)
HeapSort的实现
什么是二叉堆
一、当二叉树满足满足如下条件时，我们说这个二叉树是堆有序的：
- 每一个父结点的值都比它的子结点大（称为大顶堆）或小（称为小顶堆）
- 子结点的大小与其左右位置无关
二、二叉堆的两种实现方式
堆有序的二叉树，也可称为二叉堆。
-
二叉堆是最常见的堆结构，因此也常将二叉堆直接称为堆，可以采用如下两种方式来表示二叉堆
-
使用指针
- 二叉树的每个结点需存储三个指针，分别指向其父结点和两个子结点
-
使用数组
a. indices start at 1 下标从1开始
b. Take nodes in level order（层序遍历）
c. parent of node at k is at k/2
d. children of node at k are 2k and 2k+1
-
-
堆的数组表示
image
二叉堆的有序化
-
以大顶堆为例，有序化的过程中我们会遇到两种情况
在堆底加入一个较大元素时，我们需要由下至上恢复堆的顺序
当将根结点替换为一个较小元素时，我们需要由上到下恢复堆的顺序
1. 由下至上的堆有序化（上浮-swim）
-
条件：
- 堆的有序状态因为某个结点变的比它的父结点更大而被打破
- 即出现子节点大于父节点的情况（violation ：子节点）
-
解决方法(Eliminate the violation)
Exchange key in child with key in parent(将它与它的父结点交换来恢复堆有序)
repeat until heap order restored (交换后，这个结点比它的两个子结点都大，但这个结点仍然可能比它现在的父结点更大。我们可以一遍遍的用同样的方式来将其向上移动，直到遇到一个比它更大的父结点或到达了堆的根结点)
-
实现代码
public static void swim(int k){ while(k > 1 && less(k/2,k)){ exch(k/2,k); k = k/2; } } -
图示
image -
实现在堆中插入(Insertion in a heap)
-
Add node at end, then swim it up
public void insert(Key k){ //Key类型实现Comparable接口 pq[++N] = k; //插入到最后 swim(N); //上浮 }
-
2. 由上至下的堆有序化（下沉-sink）
-
条件
堆的有序状态因为某个结点变的比它的某个子结点更小而被打破
即出现父节点小于子节点的情况(violation : 父节点)
-
解决方法(Eliminate the violation)
Exchange key in parent with key in larger child(将它和它的子结点中较大者交换位置来恢复堆有序)
Repeat until heap order restored(交换可能会在子结点处继续打破堆的有序状态，此时可以采用相同的方式，将结点向下移动直到它的子结点都比它小或是到达了堆的底部)
-
实现代码
public void sink(int k){ while(2 * k <= N){ int j = 2 * k; if(j < N && less(j,j+1)) j++; //j指向较大子节点 if(!less(k,j)) break; //不需要继续下沉 exch(k,j); //交换父节点和较大子节点 k = j; //向下更新k } } -
图示
image -
实现在堆中返回最大值
public Key delMax(){ Key max = pq[1]; //保存最大值 exch(1,N--); //交换最后元素到1位置 sink(1); //下沉进行堆有序化 pq[N+1] = null; //将最后置为null，实现删除 return max; /将最大值进行返回 }
二叉堆实现优先队列(priority queue)
-
MaxPQ的构建
-
public class MaxPQ(Key extends Comparable<Key>>
MaxPQ()——创建一个优先队列
MaxPQ(int max)——创建固定大小的优先队列
MaxPQ(Key[] a)——从给定的数组中创建优先队列
void insert(Key k)——插入数据
Key max()——返回最大值
Key delMax()——删除最大值
boolean isEmpty()——判断队列是否为空
int size()——返回当前队列长度
-
MaxPQ的实现
/*
* 此程序是一个优先队列(priority queue)数据结构的实现
* 适用于我们无法保存大量的数据时候
*
* 此时我们使用的是二叉堆——数组实现
* 我们的下标是从1-N
*
* 1. 插入数据——insert
* 2. 返回最大值
* 3. 判断队列是否空
* 4. 当前队列长度
* */
public class MaxPQ<Key extends Comparable<Key>> {
private Key[] pq;
private int N = 0;
//创建固定大小的优先队列
public MaxPQ(int maxN){
pq = (Key[]) new Comparable[maxN+1];
}
public boolean isEmpty() {
return N == 0;
}
//插入数据
public void insert(E e) {
//插入到末尾
pq[++N] = e;
//swim
swim(N);
}
//删除最大值
public Key delMax() throws Exception{
if(isEmpty()) {
throw new Exception("pq is empty");
}
//保存最大值
Key max = pq[1];
//交换最后一个和最大值
exch(1,N--);
//下沉交换上去的值
sink(1);
pq[++N] = null;
return max;
}
//sink
private void sink(int k) {
// TODO Auto-generated method stub
//将i下沉
while(2 * k <= N) {
int j = 2 * k;
if(j < N && less(j, j+1)) j++; //j指向较大的孩子的下标
if(!less(k, j)) break;
exch(k,j); //交换父节点与较大的子孩子
k = j; //继续向下判断
}
}
//swim
private void swim(int k) {
// TODO Auto-generated method stub
while(k > 1 && less(k/2,k)) { //父小于子，则交换父子
exch(k/2, k);
k = k/2;
}
}
private void exch(int i, int j) {
// TODO Auto-generated method stub
Key tmp = pq[i];
pq[i] = pq[j];
pq[j] = tmp;
}
private boolean less(int i, int j) {
// TODO Auto-generated method stub
return pq[i].compareTo((E) pq[j]) < 0;
}
}
HeapSort的实现
-
实现方式
堆排序的过程分为两步
* Build Heap——创建一个堆，此时以大顶堆为例(Heap construction) * repeatedlly move the maximum key——(SortDown)注意的问题是
* 堆的sink操作下标是1-N * 而传入的数组下标是0-N-1 * 需要修改exch和less方法 -
第一步：Build heap using bottom-up method（利用自顶向下创建一个堆）
因为叶子节点本身就是heap order，因此不需要进行排序，因此下标从N/2开始
-
代码实现
//build heap for(k = N/2; k >= 1;k--) { sink(a,k,N); }
-
第二步:repeatedlly move the maximum key
-
思路
Remove the maximum,one at a time
leave in array, instead of nulling out
-
代码实现
//heap sort while(N >= 1) { exch(a,1,N); //交换第一个和最后一个 sink(a,1,--N); //下沉 }
-
-
HeapSort的实现
public class HeapSort { public static void sort(Comparable[] a) { int k; int N = a.length; //build heap for(k = N/2; k >= 1;k--) { sink(a,k,N); //此时的方向是从右向左 } //heap sort while(N >= 1) { exch(a,1,N); sink(a,1,--N); } } private static void sink(Comparable[] a, int k, int N) { // TODO Auto-generated method stub while(2 * k <= N) { //将父节点与较大的子节点进行交换 int j = 2 * k; if(j < N && less(a,j,j+1)) j++; //j指向较大子节点 if(!less(a,k,j)) break; exch(a,k,j); //交换父节点和最大子节点 k = j; //k继续向下进行判断 } } private static void exch(Comparable[] a, int i, int j) { i--; //因为堆是1——N，而数组是0——N-1 j--; Comparable t = a[i]; a[i] = a[j]; a[j] = t; } private static boolean less(Comparable[] a,int i, int j) { // TODO Auto-generated method stub return a[--i].compareTo(a[--j]) < 0; } } 堆排序图示
小结
堆排序算法也是一种选择排序算法,每一次删除一个最大(delMax)或最小(delMin)
整体由堆的构建、堆的交换与下沉两个步骤组成。
