C語言?如何用堆解決Topk問題
前言
本篇將詳細講解如何利用小根堆的方法解決TopK問題，這么多數據要處理，
該算法時間復度居然只需
TopK問題
TopK問題介紹：在N個數中找出最大的前K個 （比如在1000個數中找出最大的前10個）
解題方法
方法1：先排降序，前N個就是最大的。?
時間復雜度：??
方法2：N個數依次插入大堆，HeapPop?K次，每次取堆頂的數據，即為前K個。
時間復雜度：
假設N非常大，N是10億，內存中存不下這些數，它們存在文件中的。K是100，方法1 和 方法2 就都不能用了……
話說 10 億個整數，大概占用多少空間？
1G = 1024MB
1G = 1024*1024KB
1G = 1024*1024*1024Byte
要占用10億字節(jié)！所以我們來看看方法3。
方法3：
① 用前個K數建立一個K個數的小堆。
② 剩下的N-K個數，依次跟堆頂的數據進行比較。如果比堆頂的數據大，就替換堆頂的數據，再向下調整。
③ 最后堆里面的K個數就是最大的K個數。
時間復雜度：?
這里為什么使用小堆而不使用大堆？
最大的前K個數一定會比其他數要大，只要進來的數比堆頂數據大，就替代它。因為是小堆（小的在上大的在下），最大的數進去后一定會沉到下面，所以不可能存在大的數堵在堆頂導致某個數進不去的情況，數越大沉得越深。對應地，如果使用大堆就會出現一個大數堵在堆頂，剩下的數都比這個大數小，導致其他數進不來，最后只能選出最大的那一個。
代碼實現與講解
由于還沒開始講 C++ ，這里我們沒法用優(yōu)先級隊列，我們得手動自己寫一個堆來使用。當然，如果自己懶得寫，以下是 C語言 實現堆的代碼。
Heap.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap {
HPDataType* array; //指向動態(tài)開辟的數組
int size; //有效數據的個數
int capacity; //容量空間的大小
} HP;
/* 堆的初始化 */
void HeapInit(HP* php);
/* 堆的銷毀 */
void HeapDestroy(HP* php);
/* 堆的打印 */
void HeapPrint(HP* php);
/* 判斷堆是否為空 */
bool HeapIfEmpty(HP* hp);
/* 堆的插入 */
void HeapPush(HP* php, HPDataType x);
/* 檢查容量 */
void HeapCheckCapacity(HP* php);
/* 交換函數 */
void Swap(HPDataType* px, HPDataType* py);
/* 大根堆上調 */
void BigAdjustUp(int* arr, int child);
/* 小根堆上調 */
void SmallAdjustUp(int* arr, int child);
/* 堆的刪除 */
void HeapPop(HP* php);
/* 小根堆下調*/
void SmallAdjustDown(int* arr, int n, int parent);
/* 大根堆下調 */
void BigAdjustDown(int* arr, int n, int parent);
/* 返回堆頂數據*/
HPDataType HeapTop(HP* php);
/* 統(tǒng)計堆的個數 */
int HeapSize(HP* php);
Heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
/* 堆的初始化 */
void HeapInit(HP* php) {
assert(php);
php->array = NULL;
php->size = php->capacity = 0;
}
/* 堆的銷毀 */
void HeapDestroy(HP* php) {
assert(php);
free(php->array);
php->capacity = php->size = 0;
}
/* 堆的打印 */
void HeapPrint(HP* php) {
for (int i = 0; i < php->size; i++) {
printf("%d ", php->array[i]);
}
printf("\n");
}
/* 判斷堆是否為空 */
bool HeapIfEmpty(HP* php) {
assert(php);
return php->size == 0; // 如果為size為0則表示堆為空
}
/* 堆的插入 */
/* 檢查容量 */
void HeapCheckCapacity(HP* php) {
if (php->size == php->capacity) {
int newCapacity = php->capacity == 0 ? 4 : (php->capacity * 2); //第一次給4，其他情況擴2倍
HPDataType* tmpArray = (HPDataType*)realloc(php->array, sizeof(HPDataType) * newCapacity); // 數組擴容
if (tmpArray == NULL) { //檢查realloc
printf("realloc failed!\n");
exit(EXIT_FAILURE);
}
//更新他們的大小
php->array = tmpArray;
php->capacity = newCapacity;
}
}
/* 交換函數 */
void Swap(HPDataType* px, HPDataType* py) {
HPDataType tmp = *px;
*px = *py;
*py = tmp;
}
/* 大根堆上調 */
void BigAdjustUp(int* arr, int child) {
assert(arr);
// 首先根據公式計算算出父親的下標
int parent = (child - 1) / 2;
// 最壞情況:調到根，child=parent 當child為根節(jié)點時結束（根節(jié)點永遠是0）
while (child > 0) {
if (arr[child] > arr[parent]) { // 如果孩子大于父親（不符合堆的性質）
// 交換他們的值
Swap(&arr[child], &arr[parent]);
// 往上走
child = parent;
parent = (child - 1) / 2;
} else { // 如果孩子小于父親（符合堆的性質）
// 跳出循環(huán)
break;
}
}
}
/* 小根堆上調 */
void SmallAdjustUp(int* arr, int child) {
assert(arr);
// 首先根據公式計算算出父親的下標
int parent = (child - 1) / 2;
// 最壞情況:調到根，child=parent 當child為根節(jié)點時結束（根節(jié)點永遠是0）
while (child > 0) {
if (arr[child] < arr[parent]) { // 如果孩子大于父親（不符合堆的性質）
// 交換他們的值
Swap(&arr[child], &arr[parent]);
// 往上走
child = parent;
parent = (child - 1) / 2;
} else { // 如果孩子小于父親（符合堆的性質）
// 跳出循環(huán)
break;
}
}
}
void HeapPush(HP* php, HPDataType x) {
assert(php);
// 檢查是否需要擴容
HeapCheckCapacity(php);
// 插入數據
php->array[php->size] = x;
php->size++;
// 向上調整 [目標數組，調整位置的起始位置（剛插入的數據）]
SmallAdjustUp(php->array, php->size - 1);
}
/* 堆的刪除 */
/* 小根堆下調*/
void SmallAdjustDown(int* arr, int n, int parent) {
int child = parent * 2 + 1; // 默認為左孩子
while (child < n) { // 葉子內
// 選出左右孩子中小的那一個
if (child + 1 < n && arr[child + 1] < arr[child]) {
child++;
}
if (arr[child] < arr[parent]) { // 如果孩子小于父親（不符合小堆的性質）
// 交換它們的值
Swap(&arr[child], &arr[parent]);
// 往下走
parent = child;
child = parent * 2 + 1;
} else { // 如果孩子大于父親（符合小堆的性質）
// 跳出循環(huán)
break;
}
}
}
/* 大根堆下調 */
void BigAdjustDown(int* arr, int n, int parent) {
int child = parent * 2 + 1; // 默認為左孩子
while (child < n) { // 葉子內
// 選出左右孩子中大的那一個
if (child + 1 < n && arr[child + 1] > arr[child]) {
child++;
}
if (arr[child] > arr[parent]) { // 如果孩子大于父親（不符合大堆的性質）
// 交換它們的值
Swap(&arr[child], &arr[parent]);
// 往下走
parent = child;
child = parent * 2 + 1;
} else { // 如果孩子小于父親（符合大堆的性質）
// 跳出循環(huán)
break;
}
}
}
void HeapPop(HP* php) {
assert(php);
assert(!HeapIfEmpty(php));
// 刪除數據
Swap(&php->array[0], &php->array[php->size - 1]);
php->size--;
// 向下調整 [目標數組，數組的大小，調整位置的起始位置]
SmallAdjustDown(php->array, php->size, 0);
}
/* 返回堆頂數據 */
HPDataType HeapTop(HP* php) {
assert(php);
assert(!HeapIfEmpty(php));
return php->array[0];
}
/* 統(tǒng)計堆的個數 */
int HeapSize(HP* php) {
assert(php);
return php->size;
}
第三種方法的參考代碼：
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
/* 在N個數中找出最大的前K個 */
void PrintTopK(int* arr, int N, int K) {
HP hp; // 創(chuàng)建堆
HeapInit(&hp); // 初始化堆
for (int i = 0; i < K; i++) { // Step1: 創(chuàng)建一個K個數的小堆
HeapPush(&hp, arr[i]);
}
for (int i = K; i < N; i++) { // Step2: 剩下的N-K個數跟堆頂的數據比較
if (arr[i] > HeapTop(&hp)) { // 如果比堆頂的數據大就替換進堆
HeapPop(&hp); // 此數確實比堆頂大，刪除堆頂
HeapPush(&hp, arr[i]); // 將此數推進堆中，數越大下沉越深
/* 另一種寫法: 手動替換
hp.array[0] = arr[i];
SmallAdjustDown(hp.array, hp.size, 0);
*/
}
}
HeapPrint(&hp); // 打印K個數的堆
HeapDestroy(&hp); // 銷毀堆
}
/* 模擬測試 TopK */
void TestTopK() {
int N = 1000000;
int* arr = (int*)malloc(sizeof(int) * N);
srand(time(0)); // 置隨機數種子
for(size_t i = 0; i < N; i++) {
// 產生隨機數，每次產生的隨機數都mod100w，這樣產生的數一定是小于100w的
arr[i] = rand() % 1000000;
}
// 再去設置10個比100w大的數
arr[5] = 1000000 + 1;
arr[1231] = 1000000 + 2;
arr[5355] = 1000000 + 3;
arr[51] = 1000000 + 4;
arr[15] = 1000000 + 5;
arr[2335] = 1000000 + 6;
arr[9999] = 1000000 + 7;
arr[76] = 1000000 + 8;
arr[423] = 1000000 + 9;
arr[3144] = 1000000 + 10;
PrintTopK(arr, N, 10); //測試用，所以給10個
}
int main(void) {
TestTopK();
return 0;
}
運行結果
函數解讀
PrintTopK 解讀
① 準備好我們實現好的堆之后，我們就可以寫TopK的算法了。我們創(chuàng)建一個 PrintTopK 函數，函數需要接收存放數據的數組、數組的大?。∟）和要找前多少個（K）。
② 首先創(chuàng)建一個堆，用來存放K 。按照規(guī)矩我們先把 HeapInit（初始化）和 HeapDestroy（銷毀）先寫好，防止自己不小心忘記銷毀。
③ 核心步驟1：創(chuàng)建一個K個數的小堆，我們直接用 for 循環(huán)將數組中前K個值先逐個 HeapPush （堆的插入）進去。
這里不代表最后的結果，我們只是相當于 "默認" 認為這前K個數是最大的，方便我們后續(xù)進行比較替代。經過 HeapPush （堆的插入）后，這些數據會通過 SmallAdjustDown （小堆下調接口） 對數據進行相應的調整：
for (int i = 0; i < K; i++) { // Step1: 創(chuàng)建一個K個數的小堆
HeapPush(&hp, arr[i]);
}
④ 核心步驟2：除去K，將剩下的N-K個數據進行比較。我們再利用 for 循環(huán)將數組中剩下的N-K個數據進行遍歷。
這里逐個進行判斷，如果該數堆頂的數據?i＜K(max)，我們就進行替換操作。調用 HeapPop（堆的刪除）刪除堆頂的數據，給? 讓位。之后將其 HeapPush （堆的插入）推到堆中，就完成了替換的工作。值得一提的是，我們還可以不調用 Pop 和 Push 這兩個操作，手動進行替換。hp.array [ 0 ] 就表示棧頂，我們將? 賦值給它，隨后再手動進行 SmallAdjustDown （小堆下調操作），傳入相應的值即可：
for (int i = K; i < N; i++) { // Step2: 剩下的N-K個數跟堆頂的數據比較
if (arr[i] > HeapTop(&hp)) { // 如果比堆頂的數據大就替換進堆
HeapPop(&hp); // 此數確實比堆頂大，刪除堆頂
HeapPush(&hp, arr[i]); // 將此數推進堆中，數越大下沉越深
/* 另一種寫法: 手動替換
hp.array[0] = arr[i];
SmallAdjustDown(hp.array, hp.size, 0);
*/
}
}
⑤ 當 for 遍歷完所有數據之后，小堆中就保留了N個數據中最大的前K個數了。此時我們調用堆打印接口將小堆里的數據打印出來就大功告成了。
TestTopK 解讀
① 這是用來測試我們寫的TopK算法的函數。設置 N 的大小為 100w，動態(tài)內存開辟一塊可以存下這么多數據的空間：
int N = 1000000; int* arr = (int*)malloc(sizeof(int) * N);
② 隨后根據時間來置隨機數種子，將每個元素都進行隨機數的填充，每次產生的隨機數都模上100w，這樣可以保證產生的隨機數一定是小于100w的。
srand(time(0));
for(size_t i = 0; i < N; i++) {
arr[i] = rand() % 1000000;
}
③ 隨便寫幾個大于100w的數，便于測試：
// 再去設置10個比100w大的數 arr[5] = 1000000 + 1; arr[1231] = 1000000 + 2; arr[5355] = 1000000 + 3; arr[51] = 1000000 + 4; arr[15] = 1000000 + 5; arr[2335] = 1000000 + 6; arr[9999] = 1000000 + 7; arr[76] = 1000000 + 8; arr[423] = 1000000 + 9; arr[3144] = 1000000 + 10;
④ 調用我們剛才實現好的 PrintTopK 函數，遞交對應的參數后就可以進行測試了。這里為了方便測試，我們的K設置為10：
PrintTopK(arr, N, 10);
到此這篇關于C語言 如何用堆解決Topk問題的文章就介紹到這了,更多相關Topk問題內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
下面小編就為大家?guī)硪黄媪私釩語言結構體,枚舉,聯合體。小編覺得挺不錯的，現在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2021-09-09
這篇文章主要介紹了C++中指針的數據類型和運算相關知識小結,是C++入門學習中的基礎知識,需要的朋友可以參考下2015-09-09
這篇文章主要介紹了c++ 類和對象總結一,需要的朋友可以參考下2020-01-01
CreateThread()與beginthread()的區(qū)別詳細解析
很多開發(fā)者不清楚這兩者之間的關系，他們隨意選一個函數來用，發(fā)現也沒有什么大問題，于是就忙于解決更為緊迫的任務去了。等到有一天忽然發(fā)現一個程序運行時間很長的時候會有細微的內存泄露，開發(fā)者絕對不會想到是因為這兩套函數用混的結果2013-09-09
Qt使用windeployqt工具實現程序打包發(fā)布方法
本文主要介紹了Qt使用windeployqt工具實現程序打包發(fā)布方法，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
下面小編就為大家?guī)硪黄猯inux C++ 獲取文件絕對路徑的實例代碼。小編覺得挺不錯的，現在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12
這篇文章主要介紹了C++中基類和派生類之間的轉換,有助于深入理解C++面向對象程序設計,需要的朋友可以參考下2014-08-08
這篇文章主要為大家介紹了C++構造函數的初始化列表，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-12-12
今天小編就為大家分享一篇C語言數組元素的循環(huán)移位方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-07-07
下面小編就為大家?guī)硪黄獪\談C#中List<T>對象的深度拷貝問題。小編覺得挺不錯的，現在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01