參考

1. [堆結構維基百科] - https://zh.wikipedia.org/wiki/%E5%A0%86%E7%A9%8D

2. [堆結構素材] - https://github.com/wangzhione/temp/tree/master/code/struct

正文

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 = https://www.cnblogs.com/life2refuel/archive/2021/06/17/malloc(sizeof(void *) * HEAP_INIT_INT);
    if (h->data =https://www.cnblogs.com/life2refuel/archive/2021/06/17/= 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 =https://www.cnblogs.com/life2refuel/archive/2021/06/17/ 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 = https://www.cnblogs.com/life2refuel/archive/2021/06/17/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 = https://www.cnblogs.com/life2refuel/archive/2021/06/17/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 =https://www.cnblogs.com/life2refuel/archive/2021/06/17/ 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, 那會怎么樣?

期待腦經急轉彎, 有感覺評論區交流 ~

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/288071.html

標籤：其他

上一篇：平面中判斷線段與矩形是否相交

下一篇：你能拿年薪百萬幾天？

資料結構堆

參考

目錄

正文