首页 > 代码库 > 【算法】4 五张图带你体会堆算法
【算法】4 五张图带你体会堆算法
什么是堆
堆（heap），是一类特殊的数据结构的统称。它通常被看作一棵树的数组对象。在队列中，调度程序反复提取队列中的第一个作业并运行，因为实际情况中某些时间较短的任务却可能需要等待很长时间才能开始执行，或者某些不短小、但很重要的作业，同样应当拥有优先权。而堆就是为了解决此类问题而设计的数据结构。
二叉堆是一种特殊的堆，二叉堆是完全二叉树或者近似完全二叉树，二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。
当父节点的键值总是大于任何一个子节点的键值时为最大堆，当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。
为了更加形象，我们常用带数字的圆圈和线条来表示二叉堆等，但其实都是用数组来表示的。如果根节点在数组中的位置是1，第n个位置的子节点则分别在2n和2n+1位置上。
如下图所描的，第2个位置的子节点在4和5，第4个位置的子节点在8和9。所以我们获得父节点和子节点的方式如下：
PARENT(i)
1 return 小于或等于i/2的最大整数
LEFT-CHILD(i)
1 return 2i
RIGHT-CHILD(i)
1 return 2i+1
假定表示堆的数组为
最大堆除了根以外所有结点i都满足：
最小堆除了根以外所有结点i都满足：
一个堆中结点的高度是该结点到叶借点最长简单路径上边的数目，如上图所示编号为4的结点的高度为1，编号为2的结点的高度为2，树的高度就是3。
包含n个元素的队可以看作一颗完全二叉树，那么该堆的高度是
通过MAX-HEAPIFY维护最大堆
程序中，不可能所有的堆都天生就是最大堆，为了更好的使用堆这一数据结构，我们可能要人为地构造最大堆。
如何将一个杂乱排序的堆重新构造成最大堆，它的主要思路是：
从上往下，将父节点与子节点以此比较。如果父节点最大则进行下一步循环，如果子节点更大，则将子节点与父节点位置互换，并进行下一步循环。注意父节点要与两个子节点都进行比较。
如上图说描述的，这里从结点为2开始做运算。先去
因此可以给出伪代码如下：
MAX-HEAPIFY(A,i)
1 l=LEFT-CHILD(i)
2 r=RIGHT-CHILD(i)
3 if l<=A.heap-size and A[l]>A[i]
4 largest=l
5 else
6 largest=i
7 if r<=A.heap-size and A[r]>A[largest]
8 largest=r
9 if largest != i
10 exchange A[i] with A[largest]
11 MAX-HEAPIFY(A,largest) 在以上这些步骤中，调整A[i]、A[l]、A[r]的关系的时间代价为
也就是：
通过BUILD-MAX-HEAP构建最大堆
前面我们通过自顶向下的方式维护了一个最大堆，这里将通过自底向上的方式通过MAX-HEAPIFY将一个
回顾一下上面的图示，其总共有9个结点，取小于或等于9/2的最大整数为4，从4+1，4+2，一直到n都是该树的叶子结点，你发现了么？这对任意n都是成立的哦。
因此这里我们就要从4开始不断的调用MAX-HEAPIFY(A,i)来构建最大堆。
为什么会有这一思路呢？
原因是既然我们知道了哪些结点是叶子结点，从最后一个非叶子结点（这里是4）开始，一次调用MAX-HEAPIFY函数，就会将该结点与叶子结点做相应的调整，这其实也就是一个递归的过程。
图示已经这么清晰了，就直接上伪代码咯。
BUILD-MAX-HEAP(A)
1 A.heap-size=A.length
2 for i=小于或等于A.length/2的最大整数 downto 1
3 MAX-HEAPIFY(A,i)通过HEAPSORT进行堆排序算法
所谓的堆排序算法，先通过前面的BUILD-MAX-HEAP将输入数组
如何让原来根的子结点仍然是最大堆呢，可以通过从堆中去掉结点n，而这可以通过减少
通过不断重复这一过程，知道堆的大小从
上图的演进方式主要有两点：
1）将
2）不断调用MAX-HEAPIFY(A,1)对剩余的整个堆进行重新构建
一直到最后堆已经不存在了。
HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i=A.length downto 2
3 exchange A[1] with A[i]
4 A.heap-size=A.heap-size-1
5 MAX-HEAPIFY(A,1)优先队列
下一篇博文我们就会介绍大名鼎鼎的快排，快速排序啦，欢迎童鞋们预定哦~
话说堆排序虽然性能上不及快速排序，但作为一个尽心尽力的数据结构而言，其可谓业界良心呐。它还为我们提供了传说中的“优先队列”。
优先队列（priority queue）和堆一样，堆有最大堆和最小堆，优先队列也有最大优先队列和最小优先队列。
优先队列是一种用来维护由一组元素构成的集合S的数据结构，其中每个元素都有一个相关的值，称之为关键字（key）。
一个最大优先队列支持一下操作：
这里来举一个最大优先队列的示例，我曾在关于“50% CPU 占有率”题目的内容扩展 这篇博文中简单介绍过Windows的系统进程机制。
这里以图片的形式简单的贴出来如下：
在用堆实现优先队列时，需要在堆中的每个元素里存储对应对象的句柄（handle）。句柄的准确含义依赖于具体的应用程序，可以是指针，也可以是整型数。
在堆的操作过程中，元素会改变其在数组中的位置，因此在具体实现中，在重新确定堆元素位置时，就自然而然地需要改变其在数组中的位置。
一、前面的
HEAP-MAXIMUM(A)
1 return A[1]二、
HEAP-EXTRACT-MAX(A)
1 if A.heap-size < 1
2 error "堆下溢"
3 max=A[1]
4 A[1]=A[A.heap-size]
5 A.heap-size=A.heap-size-1
6 MAX-HEAPIFY(A,1)
7 return max三、
和上一个函数一样，首先判断a知否比原有的关键字更大。
然后就是老办法了，不断的将该结点与父结点做对比，如果父结点更小，那么就将他们进行对换。
相信有图示会更加清楚，于是……再来一张图。
HEAP-INCREASE-KEY(A,i,key)
1 if key < A[i]
2 error "新关键字值比当前关键字值更小"
3 A[i]=key
4 while i>1 and A[PARENT(i)] < A[i]
5 exchange A[i] with A[PARENT(I)]
6 i=PARENT(i)在包含n个元素的堆上，HEAP-INCREASE-KEY的运行时间就是
四、
MAX-HEAP-INSERT(A,key)
1 A.heap-size=A.heap-sieze+1
2 A[A.heap-size]=-10000
3 HEAP-INCREASE-KEY(A,A.hep-size,key)在包含n个元素的堆上，MAX-HEAP-INSERT的运行时间就是
总而言之，在一个包含n个元素的堆中，所有优先队列的操作时间都不会大于
实现示例
updated at 2016/09/24
自己写了demo，不过发现伟大的维基百科上有更棒的~
// C++
#include <iostream>
#include <algorithm>
using namespace std;
void max_heapify(int arr[], int start, int end) {
//建立父節點指標和子節點指標
int dad = start;
int son = dad * 2 + 1;
while (son <= end) { //若子節點指標在範圍內才做比較
if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個子節點大小，選擇最大的
son++;
if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數
return;
else { //否則交換父子內容再繼續子節點和孫節點比較
swap(arr[dad], arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len) {
//初始化，i從最後一個父節點開始調整
for (int i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
//先將第一個元素和已经排好的元素前一位做交換，再從新調整(刚调整的元素之前的元素)，直到排序完畢
for (int i = len - 1; i > 0; i--) {
swap(arr[0], arr[i]);
max_heapify(arr, 0, i - 1);
}
}
int main() {
int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
for (int i = 0; i < len; i++)
cout << arr[i] << ‘ ‘;
cout << endl;
return 0;
}// Java
public class HeapSort {
private static int[] sort = new int[]{1,0,10,20,3,5,6,4,9,8,12,17,34,11};
public static void main(String[] args) {
buildMaxHeapify(sort);
heapSort(sort);
print(sort);
}
private static void buildMaxHeapify(int[] data){
//没有子节点的才需要创建最大堆，从最后一个的父节点开始
int startIndex = getParentIndex(data.length - 1);
//从尾端开始创建最大堆，每次都是正确的堆
for (int i = startIndex; i >= 0; i--) {
maxHeapify(data, data.length, i);
}
}
/**
* 创建最大堆
* @param data
* @param heapSize需要创建最大堆的大小，一般在sort的时候用到，因为最多值放在末尾，末尾就不再归入最大堆了
* @param index当前需要创建最大堆的位置
*/
private static void maxHeapify(int[] data, int heapSize, int index){
// 当前点与左右子节点比较
int left = getChildLeftIndex(index);
int right = getChildRightIndex(index);
int largest = index;
if (left < heapSize && data[index] < data[left]) {
largest = left;
}
if (right < heapSize && data[largest] < data[right]) {
largest = right;
}
//得到最大值后可能需要交换，如果交换了，其子节点可能就不是最大堆了，需要重新调整
if (largest != index) {
int temp = data[index];
data[index] = data[largest];
data[largest] = temp;
maxHeapify(data, heapSize, largest);
}
}
/**
* 排序，最大值放在末尾，data虽然是最大堆，在排序后就成了递增的
* @param data
*/
private static void heapSort(int[] data) {
//末尾与头交换，交换后调整最大堆
for (int i = data.length - 1; i > 0; i--) {
int temp = data[0];
data[0] = data[i];
data[i] = temp;
maxHeapify(data, i, 0);
}
}
/**
* 父节点位置
* @param current
* @return
*/
private static int getParentIndex(int current){
return (current - 1) >> 1;
}
/**
* 左子节点position注意括号，加法优先级更高
* @param current
* @return
*/
private static int getChildLeftIndex(int current){
return (current << 1) + 1;
}
/**
* 右子节点position
* @param current
* @return
*/
private static int getChildRightIndex(int current){
return (current << 1) + 2;
}
private static void print(int[] data){
int pre = -2;
for (int i = 0; i < data.length; i++) {
if (pre < (int)getLog(i+1)) {
pre = (int)getLog(i+1);
System.out.println();
}
System.out.print(data[i] + " |");
}
}
/**
* 以2为底的对数
* @param param
* @return
*/
private static double getLog(double param){
return Math.log(param)/Math.log(2);
}
}感谢您的访问，希望对您有所帮助。 欢迎大家关注、收藏以及评论。
为使本文得到斧正和提问，转载请注明出处：
http://blog.csdn.net/nomasp
【算法】4 五张图带你体会堆算法