堆的概念

堆数据结构是一种数据对象,它可以被视为一棵完全二叉树结构。

堆的分类

主要用的还是二叉堆,二叉堆分为大根堆和小根堆。

大根堆,即堆顶元素是所有元素中最大的,将完全二叉树沿某条路径遍历,则得到的序列是递减的;

小根堆,即堆顶元素是所有元素中最小的,将完全二叉树沿某条路径遍历,则得到的序列是递增的。

父节点和叶节点

第i个节点的叶节点:
$\begin{cases}左叶子节点:2 \times i + 1 \\ 右叶子节点:2 \times i + 2 \end{cases}$

第i个节点的父节点:floor($\frac{i - 1}{2}$)

堆的性质

(1) 堆的插入和删除操作,运行时间为 O(logn),n 为树上结点的个数
简单证明:

假设该二叉树总共有x层,那么很明显当该二叉树为满二叉树的时候,插入和删除耗费的时间是最长的,那么则有:

2^x - 1 = n;

在最坏的情况下,我们插入一个元素的时候,是从第一层遍历到第n层(反之也一样),那么我们最多要进行的操作次数即为树的深度,而树的深度x = log(2)(n+1)(表示以2为底,以n+1为真数的对数),忽略常数,那么我们就求得插入时的最坏时间复杂度则为O(logn)级别。

(2)堆可以看成是一棵完全二叉树,除最后一层其余每层结点都是满的。

堆的实现

堆的结构体

堆是以数组的形式存储的,但在逻辑上是完全二叉树

1
2
3
4
5
typedef int DataType;
typedef struct Heap {
vector<DataType> arr;
size_t size;
}Heap;

大根堆

交换元素

1
2
3
4
5
void swap(Heap &heap, int i, int j) {
int temp = move(heap.arr[i]);
heap.arr[i] = move(heap.arr[j]);
heap.arr[j] = move(temp);
}

插入元素

1
2
3
4
5
6
7
8
void HeapInsert(Heap &heap, int index) {
//index位置与其父节点的位置进行比较

while (heap.arr[index] > heap.arr[(index - 1) / 2]) {
swap(heap, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}

更新堆

当大顶堆中某一个元素发生变化的时候,取该元素的左右子节点较大的一个,这个最大子节点再和这个修改的元素作比较,子节点大则交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
void Heapify(Heap &heap, int index,int heapSize) {
int left = index * 2 + 1;//左叶节点
while (left < heapSize) {
//取该元素的左右子节点较大的一个
int longest = left + 1 < heapSize && heap.arr[left + 1] > heap.arr[left] ? left + 1 : left;
//比较子节点和被修改元素的大小
longest = heap.arr[longest] > heap.arr[index] ? longest : index;
if (longest == index) break;
swap(heap, longest, index);
index = longest;
left = index * 2 + 1;
}
}

获取堆顶元素

1
2
3
4
5
6
7
8
int HeapTop(Heap & heap) {
int val;
if (heap.size == 0) {
return 0;
}
val = heap.arr[0];
return val;
}

删除堆顶元素

首先判断是否为空堆,如果为空堆直接返回,否则将堆首元素与堆末元素进行交换,对size进行—操作,然后调整堆的结构,使变化后的堆重新满足堆的结构。

1
2
3
4
5
6
7
8
void HeapPop(Heap& heap) {
if (heap.size == 0) {
return;
}
swap(heap, 0, heap.size - 1);
int heapSize = --heap.size;
Heapify(heap, 0, heapSize);
}

堆排序

1
2
3
4
5
6
7
8
9
void heapSort(Heap &heap) {
if (heap.size == 0) return;
int heapSize = heap.size;
swap(heap, 0, --heapSize);
while (heapSize) {
Heapify(heap, 0, heapSize);
swap(heap, 0, --heapSize);
}
}

小根堆

插入元素

1
2
3
4
5
6
void HeapInsertSmall(Heap &heap, int index) {
while (heap.arr[index] < heap.arr[(index - 1) / 2]) {
swap(heap, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}

更新堆

1
2
3
4
5
6
7
8
9
10
11
void HeapitySmall(Heap &heap, int index, int heapSize) {
int left = index * 2 + 1;
while (left < heapSize) {
int smallest = left + 1 < heapSize && heap.arr[left + 1] < heap.arr[left] ? left + 1 : left;
smallest = heap.arr[smallest] < heap.arr[index] ? smallest : index;
if (smallest == index) break;
swap(heap, smallest, index);
index = smallest;
left = index * 2 + 1;
}
}

其余的类似