文章目錄
- Topk
- 1000個數中找到最大的前十個
- 方式1：
- 方式2：
- ==方式3：==
- Topk列印函式TopkPrint
- 沒有修改的介面見 [演算法給小碼農堆魂器--鐵血柔情](https://blog.csdn.net/diandengren/article/details/121218819?spm=1001.2014.3001.5501)
- 改掉的介面
- 向上調整函式
- 向下調整函式
- 然后在Heap.h檔案中加入
Topk
在n個數中找出最大的前K個 or 在n個數中找出最小的前K個
（n>K）
1000個數中找到最大的前十個
方式1：
先排降序，前十個就是最大的，時間復雜度O(N*log2N)
方式2：
N個數依次插入大堆，PopK次，每次取堆頂的資料就是最大的前K個，時間復雜度O(N+log2N)（下篇證明）
方式3：
假設N非常大，N是10億，記憶體中存不下這些數，他們存在檔案中，k是100，那么方式1與方式2就都不可以用了，時間復雜度 O(K+(N-K)log2K)
10億整數我們看看大概消耗多少空間
1.用前K個數建立一個K個數的小堆
2.用剩下的N-K個數，依次跟堆頂的資料進行比較，如果比堆頂的資料大，就去替換堆頂的資料，在向下調整
3.最后堆里面K個數就是最大的K個數
Topk列印函式TopkPrint
void TopkPrint(int* a, int n, int k)
{
//創建一個堆
HP hp;
//堆初始化
HeapInit(&hp);
//用前K個數建立一個K個數的小堆
int i = 0;
for (i = 0; i < k; i++)
{
HeapPush(&hp,a[i]);
}
//用剩下的N-K個數，依次跟堆頂的資料進行比較，如果比堆頂的資料大，就去替換堆頂的資料，在向下調整
//替換就破壞結構了，我們用介面來實作，找到就先pop，然后push大的數就行
for (i = k; i < n ; i++)
{
//堆頂元素小于陣列中的數
if (HeapTop(&hp) < a[i])
{
//先把堆頂的數給出掉
HeapPop(&hp);
//再插入這個陣列中的數進堆
HeapPush(&hp, a[i]);
}
}
//然后列印堆即可
HeapPrint(&hp);
HeapDestroy(&hp);
}
沒有修改的介面見 演算法給小碼農堆魂器–鐵血柔情
改掉的介面
向上調整函式
//向上調整函式
void AdjustUp(HPDataType* a, int size, int child)
{
assert(a);
int parent = (child - 1) / 2;
#if HEAP
while (child > 0)
{
if (a[parent] < a[child])//父親小于孩子就交換（大堆）
{
Swap(&a[parent], &a[child]);
//交換好后重新稱呼一下孩子與父親
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
#elif !HEAP
while (child > 0)
{
if (a[parent] > a[child])//父親大于孩子就交換（小堆）
{
Swap(&a[parent], &a[child]);
//交換好后重新稱呼一下孩子與父親
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
#endif // HEAP
}
向下調整函式
//向下調整函式
void AdjustDown(HPDataType* a, int size, int parent)
{
assert(a);
//創建一個孩子變數，有兩個孩子就在這個上加1就行
int child = parent * 2 + 1;
#if HEAP
while (child < size)
{
//選大孩子
if (child + 1 < size && a[child] < a[child + 1])
{
child++;
}
//大的孩子還大于父親就交換
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
#elif !HEAP
while (child < size)
{
//選小孩子
if (child + 1 < size && a[child] > a[child + 1])
{
child++;
}
//小的孩子還小于父親就交換
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
#endif // HEAP
}
然后在Heap.h檔案中加入
//0 大堆模式 1小堆模式
#define HEAP 0
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/355377.html
標籤：其他