堆排序

• 创建成堆
• • 向上调整建堆
  • • 时间复杂度分析
  • 向下调整建堆
  • • 时间复杂度分析
• 堆排序
• top-k问题

给我一组数据，如果对他进行堆排序，那么前提就需要把它变成一个堆的形式

创建成堆

升序——建大堆
堆顶一定是最大的，那么我们每一次把堆顶的元素和堆尾的数据进行交换，那么最后一个元素为最大的元素，最后再次调整成堆的形式，这样依次可以得到次大的，最后的最后得到一个升序的数组。

降序——建小堆
堆顶一定是最小的，那么我们每一次把堆顶的元素和堆尾的数据进行交换，那么最后一个元素为最小的元素，最后再次调整成堆的形式，这样依次可以得到次小的，最后的最后得到一个降序的数组。

以降序为例

向上调整建堆

void adjustdown(HPDataType* a,int n, int father){int child = 2 * father + 1;if (child < n - 1&&a[child + 1] < a[child])child++;if (child > n - 1 || a[father] <= a[child])return;swap(&a[child], &a[father]);adjustdown(a, n, child);}

int i = 0;for (i = (n - 1 - 1) / 2; i >= 0; i--){adjustdown(a,n, i);}

时间复杂度分析

给我父节点找子节点
设该二叉树的高度为h。
向上调整建堆，是从完全二叉树的倒数第二层开始。
第h-1层，每一个节点都要调整1次。——共调整2^h-2

时间复杂度O(N)

向下调整建堆

void adjustup(HPDataType* a, int child){int father = (child - 1) / 2;if (child <= 0 || a[father] <= a[child])return;swap(&a[child], &a[father]);adjustup(a, father);}

int i = 0;for (i = 1; i <n; i++){adjustup(a, i);}

时间复杂度分析

给我子节点找父节点
我们从完全二叉树的第2层开始调整建堆。
具体的实现看下面的这张图

时间复杂度O(N*logN)

堆排序

时间复杂度O(N*logN)

void HeapSort(int* a, int n){//建小堆//向上建堆O(N)int i = 0;//for (i = (n - 1 - 1) / 2; i >= 0; i--)//{//adjustdown(a,n, i);//}//向下建堆O(N*logN)for (i = 1; i <n; i++){adjustup(a, i);}//排序O(N*logN)for (i = 0; i < n; i++){swap(&a[0], &a[n - 1 - i]);adjustdown(a, n-i-1, 0);}}

top-k问题

就是获取数据中前k个最大或者最小的数据

首先我们先建个一个k个数的堆，剩下的数据依次与堆顶的数据进行比较。
比如：我们要获取前k个最大的数据，首先建一个k个数的小堆，如果剩下的数据比堆顶的数据大，那么就进行交换。最后就得出前k个最大的数据。

节省空间

void TopK(int* a, int n, int k){//建堆int* TopKHeap = (int*)malloc(sizeof(int) * k);assert(TopKHeap);for (int i = 0; i < k; i++){TopKHeap[i] = a[i];}for (int i =(k-1-1)/2; i >= 0; i--){adjustdown(TopKHeap, k, i);}//获得前k个for (int i = k; i < n; i++){if (TopKHeap[0] < a[i]){TopKHeap[0] = a[i];adjustdown(TopKHeap, k, 0);}}}

时间复杂度O(k+(N-k)logk)