●🧑個人主頁:你帥你先說.
●📃歡迎點贊👍關注💡收藏💖
●📖既選擇了遠方，便只顧風雨兼程，
●🤟歡迎大家有問題隨時私信我！
●🧐著作權：本文由[你帥你先說.]原創，CSDN首發，侵權必究，
🧭為您導航🧭
- 📃題目
- 💡解題思路
- ??代碼實作
📃題目
什么是topK問題？簡單來講就是從n個數中取前k個最大的數，研究topK問題有什么價值嗎？
這么說吧，平常到了飯點你是不是得點外賣，比如你今天要吃西餐，那你就會在外賣系統中選擇西餐一類，系統就會幫你排出評分最高的幾家店，這就是topK問題，
💡解題思路
思路一: 首先大多數人最先想到的一定是排序，先排降序，前k個數就是最大的，假設我們用快速排序來排，那么時間復雜度就是O(N*
l
o
g
2
log_2
log2?N)，但這種方法有點多此一舉，我們只要前k個最大的，沒必要把所有數都排了，
在講思路二前你可能需要去復習一下堆的內容→資料結構--二叉樹
思路二: 可能有的人會想到之前二叉樹講的堆，N個數依次插入大堆，Popk次，每次取堆頂的資料就是前k個最大的數，此時時間復雜度為O(N+k*
l
o
g
2
log_2
log2?N)
思路三: 此時假設N非常大，思路二可能就行不通了，為什么呢？因為記憶體可能存不下那么多數，那我們怎么做呢？首先，用前k個數建立一個k個數的小堆，再用剩下的N-K個數，依次跟堆頂的資料進行比較，如果比堆頂資料大，就替換堆頂的資料，再向下調整，最后堆里面k個數就是最大的k個數，
此時時間復雜度為O(N*
l
o
g
2
K
log_2K
log2?K)
??代碼實作
結構定義
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
堆的初始化
void HeapInit(HP* hp)
{
assert(hp);
hp->a = NULL;
hp->size = hp->capacity = 0;
}
堆的向上調整
void AdjustUp(int* a, int child)
{
assert(a);
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] < a[parent])
{
HPDataType tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
堆的插入
void HeapPush(HP* hp, HPDataType x)
{
assert(hp);
if (hp->size == hp->capacity)
{
size_t newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
HPDataType* tmp = realloc(hp->a, sizeof(HPDataType)*newCapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
hp->a = tmp;
hp->capacity = newCapacity;
}
hp->a[hp->size] = x;
hp->size++;
AdjustUp(hp->a, hp->size - 1);
}
堆的向下調整
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
// 選出左右孩子中小的那一個
if (child + 1 < n && a[child + 1] < a[child])
{
++child;
}
// 如果小的孩子小于父親，則交換，并繼續向下調整
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
取堆頂元素
HPDataType HeapTop(HP* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
return hp->a[0];
}
堆的輸出
void HeapPrint(HP* hp)
{
for (int i = 0; i < hp->size; ++i)
{
printf("%d ", hp->a[i]);
}
printf("\n");
}
堆的銷毀
void HeapDestroy(HP* hp)
{
assert(hp);
free(hp->a);
hp->capacity = hp->size = 0;
}
TopK實作
void PrintTopK(int* a, int n, int k)
{
HP hp;
HeapInit(&hp);
// 創建一個K個數的小堆
for (int i = 0; i < k; ++i)
{
HeapPush(&hp, a[i]);
}
// 剩下的N-K個數跟堆頂的資料比較，比他大，就替換他進堆
for (int i = k; i < n; i++)
{
if (a[i] > HeapTop(&hp))
{
hp.a[0] = a[i];
AdjustDown(hp.a, hp.size, 0);
}
}
HeapPrint(&hp);
HeapDestroy(&hp);
}
覺得寫的不錯可以給個一鍵三連 點贊👍關注💡收藏💖(咱就是說白嫖這行為不好)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/413428.html
標籤：其他
上一篇：紅黑樹(C++實作)