数据结构中的堆结构
Knowledge Base
- 完全二叉树：
如果一棵深度为 $k$ 的二叉树，$1$ 至$ k-1$ 层的结点都是满的，即满足 $2^i-1$，只有最下面的一层的结点数小于$2^i-1$，并且最下面一层的结点都集中在该层最左边的若干位置，则此二叉树称为完全二叉树。
定义
堆结构是一种数组对象，它可以被视为一棵完全二叉树。树中每个结点与数组中存放该结点中值的那个元素相对应，如下图：
性质
下标：
第$i$个结点的父结点（parent(i)）、左结点(left(i))、右结点(right(i))的下标分别为：$\frac {i}{2}$、$2i$、$2i+1$；
大小：
堆可以分为最大堆(max-heap)和最小堆(min-heap)两种，分别满足对于任意的$i$, $A[parent(i)] >(<)A[i]$.
操作
src
//最小堆
class smallHeap {
public:
int size, maxSize, * head = NULL;
void init(int depth) {
int p = qpow(2, depth, 19260817);
head = new int[p-1];
maxSize = p - 1;
}
smallHeap(int depth) {
init(depth);
}
int getSize() {
return size;
}
bool put(int val) {
if (size == maxSize) return false;
size++;
int currentNode = size; head[currentNode] = val;
while (currentNode != 1) {
int parentNode = currentNode / 2;
if (head[parentNode] > head[currentNode]) {
int temp = head[parentNode];
head[parentNode] = head[currentNode];
head[currentNode] = temp;
currentNode = parentNode;
}
else {
break;
}
}
return true;
}
int get() {
int currentNode = 1;
int tempValue = head[currentNode];
head[currentNode] = head[size];
size--;
int parentNode = 1;
while (1) {
if (parentNode * 2 > size) break;
currentNode = (head[parentNode * 2] < head[parentNode * 2 + 1]) ? (parentNode * 2) : (parentNode * 2 + 1);
if (head[parentNode] > head[currentNode]) {
int temp = head[parentNode];
head[parentNode] = head[currentNode];
head[currentNode] = temp;
parentNode = currentNode;
}
else {
break;
}
}
return tempValue;
}
int top() { return head[1]; }
void show() {
for (int i = 1; i <= size; i++) {
cout << head[i] << " ";
}
}
};
//最大堆
class bigHeap {
public:
int size, maxSize, * head = NULL;
void init(int depth) {
int p = qpow(2, depth, 19260817);
head = new int[p-1];
maxSize = p - 1;
}
bigHeap(int depth) {
init(depth);
}
int getSize() {
return size;
}
bool put(int val) {
if (size == maxSize) return false;
size++;
int currentNode = size; head[currentNode] = val;
while (currentNode != 1) {
int parentNode = currentNode / 2;
if (head[parentNode] < head[currentNode]) {
int temp = head[parentNode];
head[parentNode] = head[currentNode];
head[currentNode] = temp;
currentNode = parentNode;
}
else {
break;
}
}
return true;
}
int get() {
int currentNode = 1;
int tempValue = head[currentNode];
head[currentNode] = head[size];
size--;
int parentNode = 1;
while (1) {
if (parentNode * 2 > size) break;
currentNode = (head[parentNode * 2] > head[parentNode * 2 + 1]) ? (parentNode * 2) : (parentNode * 2 + 1);
if (head[parentNode] < head[currentNode]) {
int temp = head[parentNode];
head[parentNode] = head[currentNode];
head[currentNode] = temp;
parentNode = currentNode;
}
else {
break;
}
}
return tempValue;
}
int top() { return head[1]; }
void show() {
for (int i = 1; i <= size; i++) {
cout << head[i] << " ";
}
}
};