数据结构【堆排序和TOP K问题】

堆的应用

堆是一种特殊的二叉树，其堆顶元素是最特殊的元素，对于堆中的任意一个节点，它的值总是不小于或不大于其父节点的值，堆具有这样的特性，究竟有什么用处呢？今天就来看看堆的应用。

1.堆排序

堆排序：利用堆来对一组无序的数据进行排序。 堆排序的原理：利用堆删除的思想来对数据进行排序。堆顶元素是堆中所有元素的最大值或最小值，每次将堆顶元素与堆中的最后一个元素交换，将堆的元素个数减一，然后再将剩余的元素进行堆的调整，重复堆删除的操作，直到堆中剩下一个元素为止，得到的就是一个有序的序列。

第一步：建堆 第二步：排序

源码如下：

void Swap(HPDataType* pLeft, HPDataType* pRight) { HPDataType temp = *pLeft; *pLeft = *pRight; *pRight = temp; } void HeapAdjust(int *array, int size, int parent) { int child = parent * 2 + 1; while (child < size) { if (child + 1 < size&&array[child + 1] < array[child]) child += 1; if (array[child]<array[parent]) { Swap(&array[child], &array[parent]); parent = child; child = parent * 2 + 1; } else{ return; } } } void HeapSort(int* array, int size) { //建堆 int root = (size - 2) / 2; for (; root >= 0; root--) { HeapAdjust(array, size, root); } //排序 int end = size - 1; while (end) { Swap(&array[0], &array[end]); HeapAdjust(array, end, 0); end--; } }

建堆的时间复杂度是NlogN， 排序的时间复杂度也是NlogN， 堆排序的时间复杂度为NlogN。

2.TOP K 问题

TOP K问题就是在一组数据中，取这组数据中前K个最大值或最小值。也就是将一组数据进行排序，然后取前K个元素。但计算机的内存是有限的，也就意味着不能对一组海量数据一次进行排序。 对于N个数据取前K个最大或最小元素： 1.我们可以先取数据的前K个进行建堆 2.再依次将（K+1）到（N）的元素和堆顶元素进行比较，如果满足条件就将堆顶元素进行替换 直到比较完最后一个元素，堆中元素就是我们要求的TOP K。

时间复杂度O(NlogK)

源码如下：

void Swap(HPDataType* pLeft, HPDataType* pRight) { HPDataType temp = *pLeft; *pLeft = *pRight; *pRight = temp; } void HeapAdjust(HPDataType* array, int size, int parent) { int child = parent * 2 + 1; while (child < size) { if (child + 1 < size && array[child] < array[child + 1]) { child += 1; } if (array[parent] > array[child]) { Swap(&array[child], &array[parent]); parent = child; child = parent * 2 + 1; } else { return; } } } void HeapTopK(HPDataType* str, int n, int k) { //创建一个数组来存储前K个数据 HPDataType* array = (HPDataType*)malloc(sizeof(HPDataType)*k); if (NULL == array) { assert(0); return; } for (int i = 0; i < k; i++) { array[i] = str[i]; } //将K个数据建一个小堆，取前K个最大的数据 int root = (k - 2) / 2; for (; root >= 0; root--) { HeapAdjust(array, k, root); } //将K+1到N的数据依次与堆顶元素比较，如果比堆顶元素大，就将堆顶元素替换成当前进行比较的元素 for (int j = 0; j < n-k; j++) { if (array[0] < str[k + j]){ array[0] = str[k + j]; HeapAdjust(array, k, 0); } } }