济宁计算机网站建设培训班,移动端网站建设的意义,wordpress广告牌,赣州市网站建设公司【数据结构】堆
堆排序
如果只是将待排数组建立一个大堆或者小堆是无法得到一个升序或者降序的数组#xff0c;因为对与一个堆#xff0c;我们没法知道同一层的大小关系。
但是#xff0c;如果建立了一个大堆#xff0c;那么堆顶元素一定是这个数组中最大的#xff0c;…【数据结构】堆
堆排序
如果只是将待排数组建立一个大堆或者小堆是无法得到一个升序或者降序的数组因为对与一个堆我们没法知道同一层的大小关系。
但是如果建立了一个大堆那么堆顶元素一定是这个数组中最大的那么将堆顶元素删除并不是真的删除而是放在数组最后用其余元素再次建立一个堆那么这个新堆的堆顶元素就是剩余元素中的最大值不断循环则个操作不就可以得到一个升序的数组。
升序建大堆降序建小堆
降序排列为例
void swap(int* a, int* b)
{int temp *a;*a *b;*b temp;
}void sort(int a[], int n)
{for (int i 1; i n; i)//建小堆{ShiftUp(a, n, i);}for (int j 1; j n; j){swap(a[0], a[n - j]);ShiftDown(a, n - j, 0);//每次将堆顶的元素数组末端的交换值向下移动重新建小堆}
}Top-K问题
求数据结合中前K个最大的元素或者最小元素
求解思路
将前k个元素建堆 如果求最大就建小堆如果求最小建大堆 将剩余n-k个元素依次和堆顶元素比较不满足某个条件就替换 某个条件是如果求前K个最大元素则是堆顶元素小于剩余元素如果求前K个最小元素则是大于剩余元素
为什么求前K个最大的元素要建小堆
举一个简单的例子在1,23,45,67中求前3个最大元素 首先前三个元素1,23建立一个小堆 4和小堆堆顶元素比较替换堆顶元素1重新建堆2,43 5和小堆堆顶元素比较替换堆顶元素2重新建堆3,45 6和小堆堆顶元素比较替换堆顶元素3重新建堆4,65 7和小堆堆顶元素比较替换堆顶元素4重新建堆5,67
替换的过程就是将原来堆中最小的元素剔除掉换一个较大的元素进去不断重复这个过程这个堆中最小的元素越来越大那么最后也只有第k大的元素可以替换掉这个堆中最小的元素那么就求出了前K个最大的元素
以求前K个最大元素为例
void TOPK(int*a,int n,int k)
{for (int i (k - 1) / 2; i 0; i--){ShiftDown(a, k, i);}for (int i k; i n; i){if (a[i] a[0]){int temp a[i];a[i] a[0];a[0] temp;for (int i (k - 1) / 2; i 0; i--){ShiftDown(a, k, i);}}}for (int i 0; i k; i){printf(%d , a[i]);}}
