數據結構堆
引用
1. [堆結構維基百科] - //zh.wikipedia.org/wiki/%E5%A0%86%E7%A9%8D
2. [堆結構素材] - //github.com/wangzhione/temp/tree/master/code/struct
目錄
1. 簡介
2. 堆結構定義
3. 堆結構實現
3.1 堆結構創建銷毀
3.2 堆結構 push 和 pop
3.3 堆結構 remove
4. 堆結構實踐
4.1 堆結構介面自測
4.2 堆結構面試小練習
5. 總結回顧
正文
1. 簡介
堆結構多數人很耳熟, 在堆排序到優先順序隊列, 系統庫的快速查找程式碼中很容易看見它的身影. 相關的資料比較
豐富, 業務上可用程式碼模板不多見. 本文重點是學以致用, 帶大家從程式碼維度來觀察和理解堆結構的工程實現.
(最小堆也被成為小頂堆, 最大堆也被稱為大頂堆)
2. 堆結構定義
#pragma once #include "struct.h" // // heap_t 堆的數據結構 // typedef struct heap * heap_t; // // heap_create - 構建特定規則的初始'小頂'堆 // fcmp : 當 fcmp(起始結點, 待比較結點) <= 0 停止調整 // return : 返回創建好的堆對象 // extern heap_t heap_create(cmp_f fcmp); extern void heap_delete(heap_t h, node_f fide); extern int heap_len(heap_t h); extern void * heap_top(heap_t h); extern bool heap_push(heap_t h, void * node); extern void * heap_pop(heap_t h); // // heap_remove - 刪除堆中索引 i 數據 // h : 堆對象 // i : 索引 i [0, heap_len()) // return : 索引為 i 的堆結點 // extern void * heap_remove(heap_t h, int i); extern void * heap_pop_push(heap_t h, void * node);
其中 struct.h 是數據結構輔助頭文件, 有心朋友可以嘗試複製和拓展
#pragma once #include <errno.h> #include <assert.h> #include <stdio.h> #include <stdarg.h> #include <stdlib.h> #include <stdint.h> #include <stddef.h> #include <stdbool.h> #include <math.h> #include <ctype.h> #include <float.h> #include <string.h> #include <limits.h> #include <inttypes.h> #ifndef CMP_F #define CMP_F // // cmp_f - 比較行為 > 0 or = 0 or < 0 // : int add_cmp(const void * now, const void * node) // typedef int (* cmp_f)(); #endif//CMP_F #ifndef NEW_F #define NEW_F // // new_f - 構建行為 // : void * rtree_new(void * node) // typedef void * (* new_f)(); #endif//NEW_F #ifndef NODE_F #define NODE_F // // node_f - 銷毀行為 // : void list_die(void * node) // typedef void (* node_f)(); #endif//NODE_F #ifndef EACH_F #define EACH_F // // each_f - 遍歷行為, node 是內部結點, arg 是外部參數 // : int echo(void * node, void * arg) { return 0; } // typedef int (* each_f)(void * node, void * arg); #endif//EACH_F // // DCODE - DEBUG 模式下的測試宏 // DCODE({ // puts("debug test start ..."); // }); // #ifndef DCODE # ifndef NDEBUG # define DCODE(code) do code while(0) # else # define DCODE(code) # endif//NDEBUG #endif//DCODE // // PERR - 列印錯誤資訊 // EXIT - 列印錯誤資訊, 並 exit // IF - 條件判斷輔助的程式退出宏 // #define PERR(fmt, ...) \ fprintf(stderr, "[%s:%s:%d][%d:%s]"fmt"\n", \ __FILE__, __func__, __LINE__, errno, strerror(errno), ##__VA_ARGS__) #define EXIT(fmt, ...) \ do { \ PERR(fmt, ##__VA_ARGS__); \ exit(EXIT_FAILURE); \ } while(0) #define IF(cond) \ if ((cond)) EXIT(#cond) // // RETURN - 列印錯誤資訊, 並 return 返回指定結果 // val : return 的東西. 填 NIL 標識 return void; // fmt : 雙引號包裹的格式化字元串 // ... : fmt 中對應的參數 // return : val // #define RETURN(val, fmt, ...) \ do { \ PERR(fmt, ##__VA_ARGS__); \ return val; \ } while(0) #define NIL #define RETNIL(fmt, ...) \ RETURN(NIL , fmt, ##__VA_ARGS__) #define RETNUL(fmt, ...) \ RETURN(NULL, fmt, ##__VA_ARGS__) #define RETERR(fmt, ...) \ RETURN(-1 , fmt, ##__VA_ARGS__)
3. 堆結構實現
3.1 堆結構創建銷毀
#include "heap.h" #define HEAP_INIT_INT (1<<5) struct heap { void ** data; int len; int cap; cmp_f fcmp; }; heap_t heap_create(cmp_f fcmp) { struct heap * h = malloc(sizeof(struct heap)); if (h == NULL) { return NULL; } h->data = malloc(sizeof(void *) * HEAP_INIT_INT); if (h->data == NULL) { free(h); return NULL; } h->cap = HEAP_INIT_INT; h->len = 0; h->fcmp = fcmp; return h; } void heap_delete(heap_t h, node_f fdie) { if (h != NULL) { return; } if (fdie != NULL && h->len > 0) { for (int i = h->len - 1; i >= 0; i--) fdie(h->data[i]); } free(h->data); free(h); }
怎麼創建; 怎麼銷毀; 何時創建; 何時銷毀. 銷毀決定了這個語言是精細手工生產工具, 還是高效智慧生產工具.
3.2 堆結構 push 和 pop
堆結構 push 和 pop 核心在於結點關係的調整. 總結有 堆結點下沉(向下調整)和堆結點上浮(向上調整).
// down - 堆結點下沉, 從上到下沉一遍 static void down(cmp_f fcmp, void * data[], int len, int x) { void * m = data[x]; for (int i = (x<<1)+1; i < len; i = (x<<1)+1) { if (i+1 < len && fcmp(data[i+1], data[i]) < 0) ++i; if (fcmp(m, data[i]) <= 0) break; data[x] = data[i]; x = i; } data[x] = m; } // up - 堆結點上浮, 從下到上浮一遍 static void up(cmp_f fcmp, void * node, void * data[], int x) { while (x > 0) { void * m = data[(x-1)>>1]; if (fcmp(m, node) <= 0) break; data[x] = m; x = (x-1)>>1; } data[x] = node; }
如何理解其中奧妙呢? 可以這麼看, 索引 i 結點的左子樹索引為 2i+1 = (x<<1)+1, 右子樹樹索引為 2i+2 = (2i+1)+1.
同樣規則索引為 i 結點的父親結點就是 (i-1)/2 = (i-1)>>1. 這就是堆結點調整的無上奧妙. 如果真要在工程角度吸
收充沛, 最需要的是臨摹和調試. 對於我們這些不具備系統演算法訓練, 演算法思維的程式設計師而言, 有時候理解演算法的
法寶是手能生巧, 溫故知新.
有了 up 上浮 和 down 下沉 兩個調整規則, 對於 push 和 pop 理解要簡單很多.
bool heap_push(heap_t h, void * node) { if (h->len >= h->cap) { void * ptr = realloc(h->data, h->cap<<1); if (ptr == NULL) { return false; } h->cap <<= 1; h->data = ptr; } up(h->fcmp, node, h->data, h->len++); return true; } static inline void heap_reduce(struct heap * h) { if (h->cap > HEAP_INIT_INT && h->cap >> 1 > h->len) { h->cap >>= 1; h->data = realloc(h->data, sizeof(void *) * h->cap); } } void * heap_pop(heap_t h) { void * top = heap_top(h); if (top && --h->len > 0) { // 尾巴結點一定比(小堆)頂結點大, 那麼要下沉 *h->data = h->data[h->len]; down(h->fcmp, h->data, h->len, 0); heap_reduce(h); } return top; }
又有了 push 和 pop , 我們構造個升級版的複合操作, pop 完之後 push
void * heap_pop_push(heap_t h, void * node) { assert(h != NULL && h->len > 0 && node != NULL); // 獲取堆頂數據準備彈出 void * top = *h->data; // 從堆頂壓入新的數據 *h->data = node; down(h->fcmp, h->data, h->len, 0); return top; }
3.3 堆結構 remove
void * heap_remove(heap_t h, int i) { if (h == NULL || h->len <= 0 || i < 0 || i >= h->len) { return NULL; } void * node = h->data[i]; // 找到結點開始走刪除操作 if (--h->len > 0) { if (h->len != i) { // 尾巴結點和待刪除結點比較 int ret = h->fcmp(h->data[h->len], node); if (ret < 0) { // '小頂'堆, 新的值比老的值小, 那麼上浮 up(h->fcmp, h->data[h->len], h->data, i); } else if (ret > 0) { // '小頂'堆, 新的值比老的值大, 那麼下沉 h->data[i] = h->data[h->len]; down(h->fcmp, h->data, h->len, i); } } heap_reduce(h); } return node; }
4. 堆結構實踐
4.1 堆結構介面自測
#include "heap.h" struct node { int value; }; static inline int node_cmp(const struct node * l, const struct node * r) { return l->value - r->value; } static void heap_print(heap_t h) { struct heap { void ** data; int len; } * obj = (struct heap *)h; // 數據列印 for (int i = 0; i < obj->len; ++i) { struct node * node = obj->data[i]; printf("%d ", node->value); } putchar('\n'); } int main(void) { heap_t h = heap_create(node_cmp); struct node a[] = { { 53 }, { 17 }, { 78 }, { 9 }, { 45 }, { 65 }, { 87 }, { 23} }; for (int i = 0; i < (int)(sizeof a / sizeof *a); ++i) heap_push(h, a + i); heap_print(h); // 數據列印 struct node * node; while ((node = heap_pop(h))) { printf("%d ", node->value); } putchar('\n'); // 重新插入數據 for (int i = 0; i < (int)(sizeof a / sizeof *a); ++i) heap_push(h, a + i); // 刪除操作 - 下沉 heap_remove(h, 0); heap_print(h); // 插入操作 heap_push(h, &(struct node){ 17 }); heap_print(h); // 刪除操作 - 上浮 heap_remove(h, 2); heap_print(h); heap_delete(h, NULL); exit(EXIT_SUCCESS); }
4.2 堆結構面試小練習
很常見面試小題尋找一堆數據中 top K . 這裡也簡單寫個例子供參考和思考.
#include "heap.h" /* 問題: 找到數據流中第 K 大元素 例如: 3 | {4, 5, 8} -> 4 3 | {4, 5, 8, 2} -> 4 3 | {4, 5, 8, 2, 3} -> 4 3 | {4, 5, 8, 2, 3, 5} -> 5 3 | {4, 5, 8, 2, 3, 5, 10} -> 5 3 | {4, 5, 8, 2, 3, 5, 10, 9} -> 8 3 | {4, 5, 8, 2, 3, 5, 10, 9, 8} -> 8 */ /* 分析: 我們用 K 個元素 小頂堆 結構 步驟: 0. 前置健壯性檢查 1. 創建一個 K 個元素小頂堆, 在其中添加 K 個元素 2. 小頂堆堆頂值最小, 讓它同待添加元素比較, 如果待添加元素值大直接替換走小頂堆下沉操作 3. 數據流比較完畢, 小頂堆頂就是 第 K 大值 複雜度: 時間複雜度: O(n*log(K)), 其中向堆中添加元素時間複雜度為 O(log(K)) 空間複雜度: O(K), 優先隊列中只用存儲 K 個元素 */ static int cmp(int * left, int * right) { return *left - *right; } int main(void) { int a[] = { 4, 5, 8, 2, 3, 5, 10, 9, 8 }; int n = sizeof(a) / sizeof(*a); int k = 3; int i = 0; heap_t h = heap_create(cmp); IF(h == NULL && (k < 0 || k > n)); for (; i < k; i++) { heap_push(h, a+i); } for (;;) { int * node = heap_top(h); printf("%d\n", *node); if (i >= n) break; if (cmp(node, a+i) < 0) { heap_pop_push(h, a+i); } i++; } heap_delete(h, NULL); // 檢查原始數據是否錯亂 for (i = 0; i < n; i++) { printf("%d ", a[i]); } putchar('\n'); exit(EXIT_SUCCESS); }
5. 總結回顧
如果有錯誤, 歡迎指正交流.
聊得很多, 大部分全是程式碼. 原因和習慣有關, 在自己逐漸成為職業寫手(不是架構師噢, 歡迎婊一下架構師)之後,
思維模式也逐漸變為直接理解程式碼或者通過程式碼理解程式碼.
簡單回顧下本文. 主要分為 數據結構堆是什麼 -> 堆結構工程實現 -> 堆結構應用小例子 三部分. 其中關於 4.2 中
面試小問題中補充個思考點, 讓大家一塊玩味玩味. top K 問題中, 如果數據是海量, 並且 K = n/2, 那會怎麼樣?
期待腦經急轉彎, 有感覺評論區交流 ~
