c++实现一个堆-包含插入删除获取

堆不要求整个数组有序，只需要关注堆顶，和堆排序不一样

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

class MYHEAP {
public:
    void push(int val) {  //插入到末尾，往前调整
        nums.push_back(val);
        heapUp();
    }

    void pop() {           //删除堆顶，往后调整
        nums[0] = nums.back();
        nums.pop_back();
        heapDown();
    }

    void heapUp()  //插入元素，从后往前调整
    {
        int index = nums.size() - 1;

        int father = (index - 1) / 2;
        while (index > 0) {
            if (nums[index] < nums[father]) {
                swap(nums[index], nums[father]);
                index = father;
                father = (father - 1) / 2;
            }
            else {
                break;
            }
        }
    }

    void heapDown()  //删除堆顶，从0往后调整
    {
        int index = 0;
        int max_index = nums.size() - 1;
        int lchild=0;
        int rchild;
        while (index < max_index) {
            lchild = 2 * index + 1;
            rchild = 2 * index + 2;
            if (lchild > max_index) break;          //不存在左孩子
            else if (rchild > max_index) {          //存在左孩子，不存在右孩子
                if (nums[index] > nums[lchild]) {
                    swap(nums[index], nums[lchild]);
                    index = lchild;
                }
                else {
                    break;
                }
            }
            else {                                  //左右孩子都存在
                int smaller = nums[lchild] <= nums[rchild] ? lchild : rchild;
                if (nums[index] > nums[smaller]) {
                    swap(nums[index], nums[smaller]);
                    index = smaller;
                }
                else {
                    break;
                }
            }
        }
    }

    void getTop() {
        cout << nums[0]<<endl;
    }

private:
    vector<int> nums;
};


int main() {
    vector<int> nums = { 2,1,6,4,3,7,0,11 };
    MYHEAP heap;
    for (int i = 0; i < 6; i++) {
        heap.push(nums[i]);
        heap.getTop();
    }

    heap.pop();
    heap.getTop();

}

关于堆排序的文章在这里