堆

堆是一种特别的二叉树，满足以下条件的二叉树，可以称之为堆： 1. 完全二叉树； 2. 每一个节点的值都必须大于等于或者小于等于其孩子节点的值。

堆具有以下的特点： * 可以在 \(\mathcal{O}(log{}N)\) 的时间复杂度内向堆中插入元素； * 可以在 \(\mathcal{O}(log{}N)\) 的时间复杂度内向堆中删除元素； * 可以在 \(\mathcal{O}(1)\) 的时间复杂度内获取堆中的最大值或最小值。

堆的分类

最大堆：堆中每一个节点的值都大于等于其孩子节点的值。所以最大堆的特性是堆顶元素（根节点）是堆中的最大值。最小堆：堆中每一个节点的值都小于等于其孩子节点的值。所以最小堆的特性是堆顶元素（根节点）是堆中的最小值。

Pasted image 20221029114514.png

对堆中的结点按层进行编号：

Pasted image 20221029114604.png

代码实现¶

class MaxHeap {
public:
    MaxHeap(int _totalSize) {
        this->_size = 0;
        this->_totalSize = _totalSize;
        this->_data = new int[this->_totalSize + 1];
    };
    ~MaxHeap() {
        delete[] this->_data;
    }
    bool push(int element) {
        this->_size++;
        if (this->_size > this->_totalSize) {
            this->_size--;
            return false;
        }
        this->_data[this->_size] = element;
        int index = this->_size;
        int parent = this->_size / 2;
        while (this->_data[index] > this->_data[parent] && index > 1) {
            swap(this->_data[index], this->_data[parent]);
            index = parent;
            parent = index / 2;
        }
        return true;
    }
    bool pop() {
        if (this->_size < 1) {
            return false;
        }
        this->_data[1] = this->_data[this->_size];
        this->_size--;
        int index = 1;
        while (index < this->_size && index <= this->_size / 2) {
            int leftChildIndex = index * 2;
            int rightChildIndex = index * 2 + 1;
            if (this->_data[index] < this->_data[leftChildIndex] || this->_data[index] < this-> _data[rightChildIndex]) {
                if (this->_data[leftChildIndex] > this->_data[rightChildIndex]) {
                    swap(this->_data[leftChildIndex], this->_data[index]);
                    index = leftChildIndex;
                } else {
                    swap(this->_data[rightChildIndex], this->_data[index]);
                    index = rightChildIndex;
                }
            } else {
                break;
            }
        }
        return true;
    }
    int size() {
        return this->_size;
    }
    int top() {
        if (this->_size == 0) return INT_MIN;
        return this->_data[1];
    }
private:
    int _size;
    int _totalSize;
    int * _data;
};

多种语言中实现了优先队列，其底层数据结构就是堆数据结构。C++ 可直接使用 priority_queue。