堆
堆是一种特别的二叉树,满足以下条件的二叉树,可以称之为堆: 1. 完全二叉树; 2. 每一个节点的值都必须大于等于或者小于等于其孩子节点的值。
堆具有以下的特点: * 可以在 \(\mathcal{O}(log{}N)\) 的时间复杂度内向堆中插入元素; * 可以在 \(\mathcal{O}(log{}N)\) 的时间复杂度内向堆中删除元素; * 可以在 \(\mathcal{O}(1)\) 的时间复杂度内获取堆中的最大值或最小值。
堆的分类
最大堆:堆中每一个节点的值都大于等于其孩子节点的值。所以最大堆的特性是堆顶元素(根节点)是堆中的最大值。 最小堆:堆中每一个节点的值都小于等于其孩子节点的值。所以最小堆的特性是 堆顶元素(根节点)是堆中的最小值。
对堆中的结点按层进行编号:
代码实现¶
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。