实现堆（push/pop）

堆可以用数组模拟。假设堆顶在arr[1]，那么任意节点 i 的左右子节点分别是 2i 和 2i+1，父节点是i/2.

堆具有以下性质：

       大顶堆：arr[i] >= arr[2i] && arr[i] >= arr[2i+1]  （i = 1,2…）

       小顶堆：arr[i] <= arr[2i] && arr[i] <= arr[2i+1]  （i = 1,2…）

 

push操作

思想：先把新元素插到堆的最后，然后自下而上，不断与父节点比较，让元素往上浮。

以大顶堆为例：

 

pop操作

思想：先用最后一个元素覆盖堆顶元素，然后再自上而下调整堆，将新的堆顶元素向下沉。

以大顶堆为例：每次选择两个子节点中的较大者进行交换。

  

代码实现

class Heap{        // 以大顶堆为例
    vector<int> heap;

public:
    Heap(){
        heap.push_back(0);    // 堆的下标从1开始
        // C++类中不能直接初始化vector<int> heap(1); 所以写在构造函数中
    }

    int size(){
        return heap.size()-1;
    }

    bool empty(){
        return size() == 0;
    }

    int top(){
        return heap[1];
    }

    void push(int value){
        heap.push_back(value);      // 把新元素插到堆的最后
        int index = heap.size()-1;  // 新元素的下标

        // 将新元素向上浮
        while(index/2 > 0 && heap[index] > heap[index/2]) { // 以大顶堆为例, 比父节点大就交换（小顶堆用<)
            swap(heap[index], heap[index/2]);
            index /= 2;
        }
    }

    void pop(){
        if(empty()) return;

        // 用最后一个元素覆盖堆顶元素
        int heap_size = heap.size()-1;  // 堆的大小(因为堆顶是v[1],所以要减1)
        swap(heap[1], heap[heap_size]); // 将堆尾元素移到堆顶
        heap.pop_back();                // 删除原来的堆顶元素
        heap_size--;

        // 将堆顶元素向下沉
        int index = 1;  // 堆顶下标
        while(true){
            int maxValueIndex = index;  // 当前节点和左右子节点这三者中最大者的下标
            // 以大顶堆为例,若父节点比子节点小，就与较大的子节点交换
            if(2*index <= heap_size && heap[index] < heap[2*index])     // 左子节点比父节点大（小顶堆用>)
                maxValueIndex = 2*index;
            if(2*index+1 <= heap_size && heap[maxValueIndex] < heap[2*index+1]) // 右节点比左节点和父节点都大（小顶堆用>)
                maxValueIndex  = 2*index+1;

            if(maxValueIndex == index) // 说明当前节点比两个子节点都大，无需再往下迭代了
                break;
            swap(heap[index], heap[maxValueIndex]);
            index = maxValueIndex;
        }
    }
};

 

 使用示例

int main(){
    Heap heap;  // 大顶堆

    int a[] = {3,2,5,4,7,9,6,8};
    // 依次入堆
    for(int i=0;i<8;i++){
        heap.push(a[i]);
        cout<<heap.top()<<" ";
    }
    cout<<endl;

    // 依次出堆(会按降序输出,但这不是堆排序,因为堆排序是在原数组上做的)
    while(!heap.empty()){
        cout<<heap.top()<<" ";
        heap.pop();
    }
}

运行结果

  

 

参考：https://mp.weixin.qq.com/s/7GeO8jjg1QUG_ofJznOsCQ