堆（heap）的原理与实现详解

本文主要包括的内容：

• 堆的原理
• 建堆、调堆
• C++中 priority_queue （Java中也有一个 PriorityQueue，有必要再补上）
• 手动建堆的实例（C++类实现）

先吐个槽O(∩_∩)O：
网站上的编辑器我总是不太会用，排版总是让我很揪心，大概是写得太少了吧。慢慢习惯吧，希望每一篇文章的排版都能进步一点点。言归正传。

堆（heap）
是一种优先队列（priority queue）。
取出元素的顺序是按照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。
特性：

1. 结构性：用数组表示的完全二叉树。
2. 有序性：任一节点的关键字是其子树所有节点的最大（小）值。
   MaxHeap、MinHeap

主要操作：建堆、判空、判满、插入、删除堆顶元素。

直接生成堆的时间复杂性是O(nlog(n))。
在线性时间复杂度O(n)下建堆：

1. 将N个元素按输入顺序存入，先满足完全二叉树（complete binary tree）的结构特性。
2. 调整节点位置：从最后一个节点的父节点开始。

这边提供一份C语言的代码，主要关注它的原理：

void PercDown( MaxHeap H, int p )
{ 
    int Parent, Child;
    ElementType X;

    X = H->Data[p]; 
    for( Parent=p; Parent*2<=H->Size; Parent=Child ) {
 Child = Parent * 2;
 if( (Child!=H->Size) && (H->Data[Child]Data[Child+1]) )
     Child++;  
 if( X >= H->Data[Child] ) break; 
 else  
     H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;
}

void BuildHeap( MaxHeap H )
{ 
  

    int i;

    
    for( i = H->Size/2; i>0; i-- )
 PercDown( H, i );
}

重要算法：上虑、下虑。

在C++中，提供了一种容器适配器（container adaptor）来实现这种数据结构，放在头文件 queue 中。
具体使用方式：

#include 
using namespace std;
...
priority_queue priQue;

主要操作有：

    bool empty() //Test whether container is empty.
    int size()   //Return size.
    void push(elem)     //Insert element.
    void emplace(elem)  //Construct and insert element.
    void pop()   //Remove top element.
    elemType top()      //Access top element.

priority_queue 默认按照严格弱序（strict weak ordering）排序规则生成最大堆，若要生成最小堆，看下面这个例子：

    #include 
    #include 
    #include 
    #include 
    using namespace std;

    int main(void) {
 priority_queue priQue;
 for (int i = 0; i < 10; i++)
     priQue.emplace(i);
 while (!priQue.empty()) {
     cout << priQue.top() << " ";
     priQue.pop();
 }
 cout << endl << endl;

 
 priority_queue, greater> minHeap;
 for (int i = 0; i < 10; i++)
     minHeap.push(i);
 while (!minHeap.empty()) {
     cout << minHeap.top() << " ";
     minHeap.pop();
 }

 system("pause");
 return 0;
    }

但许多时候，常常有其他的需求。为此，我们就需要手动建一个堆，然后就可以在堆上增加一些函数，提供我们想要的功能。
写一个最小堆类：

typedef int ElemType;
class MinHeap {
public:
    MinHeap(int capacity);  //建堆，传入堆的容量。
    ~MinHeap();
    bool isEmpty() const;
    bool isFull() const;
    bool insertElem(ElemType &elem);
    ElemType deleteTop();
private:
    ElemType *arr;
    int capacity;
    int len;    //堆中元素个数，是堆的最后一个元素的索引。
};


MinHeap::MinHeap(int capacity) {
    arr = new ElemType[capacity + 1];
    this->capacity = capacity;
    len = 0;
    arr[0] = INT_MIN;    //定义在头文件 climits 里面
}

MinHeap::~MinHeap() {
    delete[] arr;
    arr = NULL;
}

bool MinHeap::isEmpty() const {
    return 0 == len;
}

bool MinHeap::isFull() const {
    return len == capacity;
}

bool MinHeap::insertElem(ElemType &elem) {
    if (isFull()) return false;
    
    int child = ++len;
    for (; arr[child / 2] > elem; child /= 2)
 arr[child] = arr[child / 2]; //上滤 child = parent
    arr[child] = elem;
    return true;
}

ElemType MinHeap::deleteTop() {
    if (isEmpty()) return INT_MIN;  //error
    ElemType minItem = arr[1];
    
    ElemType tmp = arr[len--];
    int parent = 1;
    for (int child = 2 * parent; child <= len; child *= 2) {    //如果有左孩子
 if (child < len && arr[child] > arr[child + 1]) child++;    //child指向数据值较小的子节点。
 if (tmp <= arr[child]) break;
 else arr[parent] = arr[child];  //下滤。
 parent = child;
    }
    arr[parent] = tmp;
    return minItem;
}

比如，如果要打印从一个给定索引到根节点的路径，就可以在 MinHeap 中增加一个函数，代码如下：

class MinHeap {
public:
    void printPath(int index);
}

void MinHeap::printPath(int index) {
    if (index > len) {
 cout << "没有这个元素" << endl;
 return;
    }
    cout << arr[index];
    while (index > 1) {
 index /= 2;
 cout << " " << arr[index];
    }
    cout << endl;
}

好了，就写到这里吧。
慕友若有什么高见，可在下面回复。
祝开心。