1.堆
堆是一种特殊的树,,只要满足这两点,它就是一个堆
- 堆是一个完全二叉树;
- 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。
对于每个节点的值都大于等于子树中每个节点值的堆,叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆,叫作“小顶堆”。

其中第1个和第2个是大顶堆,第3个是小顶堆,第4个不是堆。除此之外,从图中还可以看出来,对于同一组数据,可以构建多种不同形态的堆。
2.实现一个堆
完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为不需要存储左右子节点的指针,单纯地通过数组的下标,就可以找到一个节点的左右子节点和父节点。
数组中下标为i的节点的左子节点,就是下标为i*2的节点,右子节点就是下标为i*2+1的节点,父节点就是下标为i/2的节点。
2.1 结构体定义及初始化
#define MaxSize 200 typedef int ElemType; // 采用动态数组定义 // 注意:0号不存储元素 typedef struct { ElemType* data; int length; int maxSize; }HeapList;
// 注意:0号不存储元素 void initHeap(HeapList& L, int initSize) { L.data = (ElemType*)malloc(sizeof(ElemType) * (initSize+1)); L.length = initSize; L.maxSize = MaxSize; }
2.2 插入元素
(1)堆化( heapify)
不满足堆要求,就需要进行调整,让其重新满足堆的特性,这个过程就叫做堆化。
堆化两种,从下往上和从上往下。
堆化方法:顺着节点所在的路径,向上或者向下,对比,然后交换。
从下往上堆化:以让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系,就互换两个节点。

(2) 堆化(插入)代码
// 从下往上堆化 void insertElemHeap(HeapList& L, ElemType data) { if (L.length >= L.maxSize) return; // 将新插入数据放到最后 L.length++; L.data[L.length] = data; // 自下往上堆化 // 让新插入的结点与父节点比对大小, // 如果不满足子结点小于等于父结点的大小关系,就互换两个结点 int i = L.length; while (i / 2 > 0 && L.data[i] > L.data[i / 2]) { // 交换两个元素 ElemType tmpElem = L.data[i]; L.data[i] = L.data[i / 2]; L.data[i / 2] = tmpElem; // 更新i下标 i = i / 2; } }
2.3 删除堆顶元素
任何节点的值都大于等于(或小于等于)子树节点的值,可以发现,堆顶元素存储的就是堆中数据的最大值或者最小值。
(1)数组空洞
当删除堆顶元素之后,就需要把第二大的元素放到堆顶,那第二大元素肯定会出现在左右子节点中。然后再迭代地删除第二大节点,以此类推,直到叶子节点被删除。

(2)从上往下堆化
- 把最后一个节点放到堆顶,然后利用同样的父子节点对比方法。
- 对于不满足父子节点大小关系的,互换两个节点,
- 并且重复进行这个过程,直到父子节点之间满足大小关系为止。

(3)代码
// 从上往下堆化,从标号为k的元素开始堆化 void heapify(HeapList& L, int k, int len) { while (true) { // 寻找父结点的两个子结点中最大的一个 int maxPos = k; if (k * 2 <= len && L.data[k] < L.data[2 * k]) maxPos = k * 2; if (k * 2 + 1 <= len && L.data[maxPos] < L.data[2 * k + 1]) maxPos = k * 2 + 1; // 若子结点比自己都小,父结点就是最大的 if (maxPos == k) break; // 交换元素 ElemType tmpElem = L.data[k]; L.data[k] = L.data[maxPos]; L.data[maxPos] = tmpElem; // 更新 k = maxPos; } }
void removeHeapTopElem(HeapList& L, ElemType& elem) { if (L.length == 0) return; elem = L.data[1]; L.data[1] = L.data[L.length]; L.length--; heapify(L, 1, L.length); }
3.堆排序
可以把堆排序的过程大致分解成两个大的步骤, 建堆和排序。
3.1 建堆
首先将数组原地建成一个堆。所谓“原地”就是,不借助另一个数组,就在原数组上操作。
- 是从后往前处理数组,并且每个数据都是从上往下堆化。

()代码
// 从数组,原地建堆 void buildHeap(HeapList& L) { for (int i = L.length / 2; i >= 1; i--) { heapify(L, i, L.length); } }
3.2 排序
(1)步骤
- 建堆结束之后,数组中的数据已经是按照大顶堆的特性来组织的。
- 数组中的第一个元素就是堆顶,也就是最大的元素。
- 把它跟最后一个元素交换,那最大元素就放到了下标为n的位置。

(2)代码
void heapSort(HeapList& L) { // 建立大顶堆 buildHeap(L); printSqList(L); // 排序 int tmpElem = 0; for (int i = L.length; i > 1; i--) { tmpElem = L.data[i]; L.data[i] = L.data[1]; L.data[1] = tmpElem; heapify(L, 1, i - 1); } }
(3)复杂度
- 整个堆排序的过程,都只需要极个别临时存储空间,所以堆排序是原地排序算法。
- 堆排序包括建堆和排序两个操作,建堆过程的时间复杂度是O(n),排序过程的时间复杂度是O(nlog n),所以,堆排序整体的时间复杂度是O(nlog n)。
- 堆排序不是稳定的排序算法,因为在排序的过程,存在将堆的最后一个节点跟堆顶节点互换的操作,所以就有可能改变值相同数据的原始相对顺序。