简介

当一棵二叉树的每个结点都大于它的两个子结点时，被称为堆有序；

如果我们用指针来表示堆有序的二叉树，那么每个元素都需要三个指针来找到它的上下结点；但是如果我们使用完全二叉树，只用数组而不需要指针就可以表示；

什么是最小堆呢？

最小堆就是在二叉堆的基础上，符合了每个结点都比他的子结点要小的规则！

我们会遇到这两种情况，这也是最小堆中特别要注意的两种实现：

• 上浮：从下至上恢复堆的顺序，在当某个节点的优先级上升时；
• 下沉：从上至下恢复的顺序，当某个节点的优先级下降的时候；

我们可以从下面的图中观察最小堆是如何运行的：

只要不满足小的规则就交换

实现

1.上浮

先看上浮，其思想就是，因为是从下至上，所以根据当前结点，算出父亲结点，然后跟父亲结点进行比较，如果子结点小的话，则需要进行相互交换，反之不用，直到循环到下标到达结尾；

/** *  将end到0的数据都上浮 * *  @param end */void MinHeap::shiftUp(int end) {    int i = end;    while (i > 0) {        int parent = i % 2 == 0 ? i/2 - 1 : i/2;        if (heap[i] < heap[parent]) {            swap(&heap[i], &heap[parent]);            i = parent;        }        else {            --i;        }    }}

2.下沉

接着看下沉，其思想就是，因为是从上至下，所以根据当前结点，算出左右子结点，然后跟当前结点进行比较，如果左右结点小，这里需要注意的是，取左右子结点中小的进行交换，因为其中必然会有三者之中的最小值，反之不用，直到循环到下标到达0；

/** *  将start到end的数据都往下沉 *  将子结点和父结点进行比较 * *  @param start <#start description#> *  @param end   <#end description#> */void MinHeap::shiftDown(int start, int end) {    int i = start;    while (i < end) {        int lchild = i*2 + 1, rchild = i*2 + 2;                if ((heap[i] > heap[lchild] && lchild < currentSize) || (heap[i] > heap[rchild] && rchild < currentSize)) {            bool leftSmall = heap[lchild] < heap[rchild];                        if (leftSmall) {                swap(&heap[i], &heap[lchild]);                i = lchild;            }            else {                swap(&heap[i], &heap[rchild]);                i = rchild;;            }        }        else {            ++i;        }    }}

3.插入删除

还有一个需要注意的点是插入删除；

• 插入：插到数组的最后一个位置上，增加堆大小，并且上浮；
• 删除：将数组头元素用数组尾元素进行替换，减小堆大小，并且下沉；

4.整体实现

////  main.cpp//  Heap////  Created by George on 16/11/1.//  Copyright © 2016年 George. All rights reserved.//#include 
    
     #define DefaultSize 10#define Log(content) { std::cout << "Log:" << content << std::endl; }class MinHeap {public:    MinHeap(int size = DefaultSize);    ~MinHeap();        inline bool isEmpty() {        return currentSize == 0;    };        inline bool isFull() {        return currentSize == maxSize;    };        bool insert(const int value);    bool removeMin();    int poll();        void shiftDown(int start, int end);    void shiftUp(int end);        void toString();    private:    int * heap;    int currentSize;    int maxSize;        void swap(int *num1, int *num2);};MinHeap::MinHeap(int size) : currentSize(0) {    heap = new int[size];    maxSize = size > DefaultSize ? size : DefaultSize;}MinHeap::~MinHeap() {    }void MinHeap::toString() {    for (int i = 0; i < currentSize; ++i) {        std::cout << heap[i] << std::endl;    }}void MinHeap::swap(int *num1, int *num2) {    int temp = *num1;    *num1 = *num2;    *num2 = temp;}/** *  将start到end的数据都往下沉 *  将子结点和父结点进行比较 * *  @param start <#start description#> *  @param end   <#end description#> */void MinHeap::shiftDown(int start, int end) {    int i = start;    while (i < end) {        int lchild = i*2 + 1, rchild = i*2 + 2;                if ((heap[i] > heap[lchild] && lchild < currentSize) || (heap[i] > heap[rchild] && rchild < currentSize)) {            bool leftSmall = heap[lchild] < heap[rchild];                        if (leftSmall) {                swap(&heap[i], &heap[lchild]);                i = lchild;            }            else {                swap(&heap[i], &heap[rchild]);                i = rchild;;            }        }        else {            ++i;        }    }}/** *  将end到0的数据都上浮 * *  @param end */void MinHeap::shiftUp(int end) {    int i = end;    while (i > 0) {        int parent = i % 2 == 0 ? i/2 - 1 : i/2;        if (heap[i] < heap[parent]) {            swap(&heap[i], &heap[parent]);            i = parent;        }        else {            --i;        }    }}/** *  删除最小值，也就是堆顶，用最大值替代，并且下沉 * *  @return <#return value description#> */bool MinHeap::removeMin() {    if (currentSize == 0) {        Log("current size is 0!");        return false;    }    heap[0] = heap[currentSize-1];    --currentSize;    shiftDown(0, currentSize-1);    return true;}/** *  插入值后要进行上浮 * *  @param value <#value description#> * *  @return <#return value description#> */bool MinHeap::insert(const int value) {    if (currentSize == maxSize) {        int *nHeap = heap;        heap = new int(maxSize + 10);        for (int i = 0; i < maxSize; ++i) {            heap[i] = nHeap[i];        }        delete [] nHeap;        Log("heap is resize!");    }    heap[currentSize++] = value;    shiftUp(currentSize-1);    return true;}/** *  取得堆顶值 * *  @return <#return value description#> */int MinHeap::poll() {    if (isEmpty()) {        Log("heap is null!");        return -1;    }    return heap[0];}int main(int argc, const char * argv[]) {    // insert code here...        MinHeap Heap;        Log("------------Insert------------");    int arr[8] = {8, 7, 6, 5, 4, 3, 2, 1};    for (int i = 0; i < 8; i++) {        Heap.insert(arr[i]);    }        Heap.toString();        Log("------------Remove------------");    Heap.removeMin();        Heap.toString();        Log("------------Get------------");    std::cout << "poll:" << Heap.poll() << std::endl;        return 0;}
    

看结果：