C语言堆排序
清欢有道 人气:01.堆的概念及结构
如果有一个关键码的集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉树(二叉树具体概念参见——二叉树详解)的顺序存储方式存储在一个一维数组中,并满足:Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0,1,2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
堆的性质:
- 堆中某个节点的值总是不大于或不小于其父节点的值;
- 堆总是一棵完全二叉树。
2.堆的实现
堆的实现请参见——二叉树详解(堆的实现)
2.1 堆的向下调整算法
(此文章都已建小堆为例)
向下调整算法前提:当前树左右子树都是小堆
核心思想:选出左右孩子中小的那个,和父亲交换,小的往上浮,大的往下沉,这里是小堆,如果是大堆则相反。
代码实现
void swap(int *x, int *y) { int temp = *x; *x = *y; *y = temp; } //堆向下调整算法 void AdjustDown(int *a, int n, int root) { int parent = root; int child = parent * 2 + 1; while (child<n) { //保证孩子节点child为两个孩子中的最小值;保证不越界 if (a[child] > a[child + 1] && child+1 < n) ++child; if (a[child] < a[parent]) { swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else break; } }
2.2 堆的向上调整算法
使用场景:向上调整算法适用于向堆中插入数据,当向堆中插入数据就可能会导致堆失去大堆或者小堆的性质,此时需要重新调整,向上调整的思路与向下调整算法的思路类似,向上调整算法只需要从插入结点位置开始和父节点比较。
图示:
代码实现:
void AdjustUp(int *a, int child) { int parent = (child - 1) / 2; while (child > 0) { if (a[parent] > a[child]) { swap(&a[parent], &a[child]); child = parent; parent = (child - 1) / 2; } else break; } }
2.3 建堆(数组)
从最后一个非叶子节点位置行依次开始调整,如图:
代码实现:
int parent = (n-2) / 2; //首先对每一个非叶子节点进行一次向下调整算法,保证每个非叶子节点的 //孩子都小于它的父节点,然后可得到最小值,就在堆的顶端的父节点(也叫做建小堆) while (parent >= 0) { AdjustDown(a, n, parent); --parent; }
2.4 堆排序
升序建大堆,降序建小堆
void HeapSort(int *a, int n) { int parent = (n-2) / 2; //首先对每一个非叶子节点进行一次向下调整算法,保证每个非叶子节点的 //孩子都小于它的父节点,然后可得到最小值,就在堆的顶端的父节点(也叫做建小堆) while (parent >= 0) { AdjustDown(a, n, parent); --parent; } int end = n-1; while (end>0) { //将堆顶的数与最后的end,以此循环,进行交换就可得到有序序列 //注意:建小堆,得到降序序列 swap(&a[end], &a[0]); AdjustDown(a, end, 0); --end; } }
2.5 堆排序的时间复杂度
所以建堆时间复杂度为O(N);
向下调整算法时间复杂度 O(logN);
所以堆排序的时间复杂度为 O(N*logN)
加载全部内容