堆

优先队列

定义

父节点一定是其所有子孙节点的最值的一颗完全二叉树（该定义待补充，存疑）

存储结构

二叉堆

class Heap {
public:
    int* heap;
    int size;
    Heap(int data[], int size) {
        this->size = 0;
        heap = new int[size];
        for (int i = 0;i < size;i++)
            this->push(data[i]);
    }
    void push(int x) {
        int index = size++;
        while (index > 0) {
            int parentIndex = (index + 1) / 2 - 1;
            if (heap[parentIndex] < x) break;
            heap[index] = heap[parentIndex];
            index = parentIndex;
        }
        heap[index] = x;
    }
    int pop() {
        int result = heap[0];//获取最值
        int x = heap[--size];//虽然没有对根节点直接赋值，但是下面等效为根节点值为x
        int index = 0;
        //和子节点比较大小，不断向下维护堆
        while ((index + 1) * 2 <= size) {
            int lIndex = (index + 1) * 2 - 1;
            int rIndex = (index + 1) * 2;
            int MinIndex = lIndex;
            if (rIndex <= size && heap[rIndex] < heap[MinIndex])
                MinIndex = rIndex;
            if (heap[MinIndex] >= x) break;
            heap[index] = heap[MinIndex];
            index = MinIndex;
        }
        heap[index] = x;
        return result;
    }
};

D-堆

斐波那契堆

二项式堆

优先队列

该项编辑不完全

定义

可以插入新元素 可以快速取出所有元素的最值