Test Message

[模板] Heap(堆積)

模板

Heap 主結構

#define HEAPSIZ 1024

typedef struct
{
    /* your data here */
}Node;

typedef struct
{
    Node val[HEAPSIZ];
    int last;
}Heap;

inline int cmp(register const Node* lhs, register const Node* rhs)
{
    /* compare values here */
}

inline void swap(register Node* lhs, register Node* rhs)
{
    Node tmp = *lhs;
    *lhs = *rhs, * rhs = tmp;
}

void insNode(register Heap* heap, register Node val)
{
    heap->val[++heap->_last] = val;
    int now = heap->_last, base = now >> 1;
    while (base && cmp(&heap->val[base], &heap->val[now]) < 0)
        swap(&heap->val[now], &heap->val[base]), now >>= 1, base >>= 1;
}

void delNode(register Heap* heap)
{
    swap(&heap->val[1], &heap->val[heap->_last--]);
    int now = 1, derived = 2;
    while (derived <= heap->_last)
    {
        if (cmp(&heap->val[derived], &heap->val[derived + 1]) < 0 && derived < heap->_last) derived++;
        if (cmp(&heap->val[derived], &heap->val[now]) < 0) break;
        swap(&heap->val[derived], &heap->val[now]), now <<= 1, derived <<= 1;
    }
}

概述

本組模板為堆積模板，可以用來實現簡單的最大 / 最小堆。

結構

Node

本結構使用者自定義的資料，如果你只要使用編譯器預設的資料型態(int/double…)，你可以將 Node 直接定義成該型態

typedef int Node;

這樣在新增節點時會比較方便。

Heap

本結構為堆積的主結構，使用他來宣告一個新的堆積，結構中的 _last 為保證結構正運作的必要參數，請不要任意更改它除非你清楚了解它的作用。

函式

cmp()

本函式為比較函式。

參數
lhs (const Node*)

本參數為比較資料的左項。

rhs (const Node*)

本參數為比較資料的右項。

回傳值

回傳比較後的結果。

insNode()

本函式會新增一筆資料至目標堆積。

參數
heap (Heap*)

本參數為目標堆積。

val (Node)

本參數為存入目標堆積的元素。

回傳值

本函式無回傳值。

delNode()

本函式會將目標堆積頂端的元素刪除。

參數
heap (Heap*)

本參數為目標堆積。

回傳值

本函式無回傳值。

其他

HEAPSIZ

此巨集用來定義元素的數量上限。

實例

#include <stdio.h>
#define HEAPSIZ 1024

typedef int Node;

typedef struct
{
    Node val[HEAPSIZ];
    int _last;
}Heap;

inline int cmp(register const Node* lhs, register const Node* rhs)
{
    return *lhs - *rhs;
}

inline void swap(register Node* lhs, register Node* rhs)
{
    Node tmp = *lhs;
    *lhs = *rhs, * rhs = tmp;
}

void insNode(register Heap* heap, register Node val)
{
    heap->val[++heap->_last] = val;
    int now = heap->_last, base = now >> 1;
    while (base && cmp(&heap->val[base], &heap->val[now]) < 0)
        swap(&heap->val[now], &heap->val[base]), now >>= 1, base >>= 1;
}

Node delNode(register Heap* heap)
{
    swap(&heap->val[1], &heap->val[heap->_last--]);
    int now = 1, derived = 2;
    while (derived <= heap->_last)
    {
        if (cmp(&heap->val[derived], &heap->val[derived + 1]) < 0 && derived < heap->_last) derived++;
        if (cmp(&heap->val[derived], &heap->val[now]) < 0) break;
        swap(&heap->val[derived], &heap->val[now]), now <<= 1, derived <<= 1;
    }
}

int main()
{
    Heap heap = { 0 };
    insNode(&heap, 5);
    insNode(&heap, 9);
    insNode(&heap, 1);
    insNode(&heap, 9);
    insNode(&heap, 7);
    printf("%d\n", heap.val[1]);
    delNode(&heap);
    printf("%d\n", heap.val[1]);
    delNode(&heap);
    printf("%d\n", heap.val[1]);
    delNode(&heap);
    printf("%d\n", heap.val[1]);
    delNode(&heap);
    printf("%d\n", heap.val[1]);
    delNode(&heap);
    return 0;
}
編譯運行結果

9
9
7
5
1

注意事項

  • 在區域變數裡宣告新的 Heap 時必須將其初始化

    Heap heap = { 0 };

    否則會因為存取違規而出現 runtime error;

  • 測試階段，謹慎使用。

更新紀錄

無