堆的概念
堆是一种完全二叉树(除了最后一层每个节点的子节点都是满的,最后一层的节点也是集中在左边)
虽然堆是一棵二叉树,但也由于它是一棵完全二叉树的原因,可以使用一个数组来表示堆。(层次遍历)
我们常用到的堆是最大堆和最小堆
最小堆
最小堆要求,对于任意一个父结点来说,其子结点的值都大于这个父节点。

对于这个最小堆,可以用数组表示为[1,3,30,22,10,50]
最大堆
最大堆和最小堆相反,对于任意一个父结点来说,其子结点的值都小于这个父节点。
堆的操作
插入
我们看如何构建一个最小堆:
对于[30,15,5,11,22,2]

可以看出,我们依次按数组的顺序放入二叉树的节点,一旦出现子节点比父节点的值小,交换子节点和父节点。
我们称这个操作为向上堆化,堆化后的数组为[2,11,5,30,22,15]
删除
将堆树中待删除的节点A与堆树中的最后一个节点B互换,然后调整节点B到合适的位置,最后从堆树中删除排在堆数组最后的节点A。
不过在堆这个数据结构中,我们通常只需要删除堆顶元素。


堆的应用
优先级队列
实现优先级队列的方法有很多,但是用堆来实现是最直接、最高效的。堆和优先级队列非常相似,一个堆就可以看作一个优先级队列。从优先级队列中取出优先级最高的元素,就相当于取出堆顶元素。
堆排序
堆排序实际上就是不断获取堆顶元素。
对于最大堆来说,我们知道最大堆的队首元素是整个堆最大的元素,当我们删除并得到堆顶元素时,剩下的元素会重新堆化,得到一个新的堆顶元素,这样不断删除并获取堆顶元素,最终拿到的就是一个从大到小的有序序列。
当然,用数组代表堆,我们在排序的时候可以不必删除元素,只需要将原堆顶元素移动到数组末尾,将剩下的元素重新堆化,然后重复该步骤,最后就能得到一个从小到大排序的数组。
附:代码示例
实现一个完整的最大堆并堆排序一个数组
public class MaxHeap {
private int[] heap;
private int size;
// 用数组来初始化一个堆
public MaxHeap(int[] source){
heap = source;
size = source.length;
heapify();
}
public int get(int index){
return heap[index];
}
public int size() {
return size;
}
//移除一个元素,并从这个元素开始向下堆化
public int removeAt(int index){
int node = heap[index];
swap(index,size-1);
size--;
downShift(index);
return node;
}
//构建堆
public void heapify(){
for(int i = 0; i < size; i++){
int position = i;
upShift(position);
}
}
//向上堆化
public void upShift(int position){
int parent = getParent(position);
while (position>0 && (heap[position]>heap[parent])){
swap(position,parent);
position = parent;
parent = getParent(position);
}
}
//向下堆化
public void downShift(int position){
int children1 = position*2+1;
int children2 = position*2+2;
while (children1<size){
int toSwap = children1;
if(children2<size){
toSwap = heap[children1]>heap[children2]?children1:children2;
}
if(heap[toSwap]>heap[position]){
swap(position,toSwap);
position = toSwap;
children1 = position*2+1;
children2 = position*2+2;
}else break;
}
}
public void swap(int source,int destination){
int cache = heap[source];
heap[source] = heap[destination];
heap[destination] = cache;
}
/**
* 计算父节点下标
*/
private int getParent(int child) {
return (child + 1) / 2 - 1;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
for (int i = 0;i<size;i++){
sb.append(heap[i]);
if(i!=size-1) sb.append(",");
}
return sb.append("]").toString();
}
public static void main(String[] args) {
MaxHeap heap = new MaxHeap(new int[]{30,15,5,11,22,2});
System.out.println(heap);
while (heap.size()!=0){
//堆排序得到一个序列
int head = heap.removeAt(0);
System.out.println(head);
}
//操作完后数组里元素的是从小到大排序的
System.out.println(Arrays.toString(heap.heap));
}
}
运行结果:
[30,22,5,11,15,2]
30
22
15
11
5
2
[2, 5, 11, 15, 22, 30]
堆排序算法Java实现
实际的堆排序中,我们肯定不用写这么长一段代码,专门把排序的逻辑提取出来就行了:
把数组看成一个最大堆(无序部分)和一个有序部分,每次将无序部分堆化一次(第一次构建堆的堆化是最耗时的,后面的堆化只需要向下堆化就好),然后第一个元素就是无序部分中最大的元素,与无序部分最后一个元素进行交换,然后并入有序部分
代码参考堆排序算法思路以及Java实现_long_lance的博客-CSDN博客,但是这里面的代码有错误,我进行了修改。
public class HeapSorting {
public static void main(String[] args) {
int[] a=new int[]{9,8,1,5,6,10,2};
Sort(a);
for(int i:a){
System.out.println(i);
}
}
//通过递归向下堆化
public static void MaxHeapify(int[] a,int index,int size){
int l=2*index;
int r=2*index+1;
int largest=index;
if(l<=size && a[l]>a[index]){
largest=l;
}
if(r<=size && a[r]>a[largest]){
largest=r;
}
if(largest!=index){
int temp=a[largest];
a[largest]=a[index];
a[index]=temp;
MaxHeapify(a,largest,size);
}
}
//数组堆化,注意上面实现堆的代码中构建堆是通过向上堆化,我们可以优化成将所有非叶节点向下堆化
public static void HeapBuild(int[] a){
for(int i=(a.length-1)/2;i>=0;i--){
MaxHeapify(a,i,a.length-1);
}
}
public static void Sort(int[] a){
//构建堆
HeapBuild(a);
for(int i=a.length-1;i>=1;i--){
//每次将堆顶元素交换到未排序部分末尾,然后再向下堆化
int temp=a[i];
a[i]=a[0];
a[0]=temp;
MaxHeapify(a,0,i-1);
}
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%b8%a6%e6%9c%89%e4%bc%98%e5%85%88%e7%ba%a7%e7%9a%84%e5%ae%8c%e5%85%a8%e4%ba%8c%e5%8f%89%e6%a0%91-%e5%a0%86/