C語言實現大頂堆的示例代碼

Posted on by

堆的實現

1.堆結構

邏輯結構上類似於 一棵 “樹”

2.堆的種類

大頂堆結構： 一種特殊的樹：其每個子節點均比母節點要小

小頂堆結構： 同理：其每個子節點均比母節點要大

結構圖示：

3.大頂堆代碼實現

這裡實現堆 用循序表的方式

①初始化：

typedef int Heaptype;
 
typedef struct Heap
{
    Heaptype* head;   
    int size;         //記錄堆總容量 
    int capacity;     //記錄當前數據總個數
}Heap;
 
//堆的初始化
void Heap_Init(Heap* pphead)
{
    assert(pphead);
    pphead->head = NULL;
    pphead->size = 0;
    pphead->capacity = 0;
}

②插入數據：

實現細節：數據在插入的同時，要進行數據結構的調整，使樹頂始終保持最大數

如果新插入節點比母節點大的話，要進行交換 ，因此將這個調整結構的環節獨立出來

即：“向上調整”。

 向上調整：因為插入數據時：新數據默認儲存在順序表尾，因此其邏輯上是在堆的底部，

所以，當新數據比母節點大時，它將與邏輯上處於其上方的母節點交換，稱為

向上調整。

註：向上調整有時不止調整一次 ，還有可能調整多次，直到每個節點都在其相應位置 。

流程圖解：

大頂堆插入流程

細節點：因為數據是以順序表的方式儲存，所以子節點的下標與母節點的下標符合

公式：parent = (child – 1)/2 ；(按照此公式帶入計算就理解瞭) 

//向上調整
void adjust_up(Heap* pphead)
{
    int child = pphead->capacity;
    int parent = (child - 1) / 2;
    for (; pphead->head[parent] < pphead->head[child];)//判斷是否符合大頂堆
    {
        swap(&(pphead->head[parent]),&(pphead->head[child]));//進行交換
        child = parent;
        parent = (child - 1) / 2;
    }
}
 
//插入數據
void Heap_push(Heap* pphead, Heaptype data)
{
    assert(pphead);
    //判斷是否滿容量並擴容
    Heap_realloc(pphead);
    pphead->head[pphead->capacity] = data;
    //向上調整
    adjust_up(pphead);
    pphead->capacity++;
}

③刪除數據：為瞭避免因為直接刪除頭部數據導致整個堆的結構打亂，

這裡先將頭部數據與尾數據交換，然後將尾部數據刪除，接著使用“向下調整”，即：將換上來的頂部數據向下與其子節點比較調整，直至符合大頂堆結構為止。

註：1.大頂堆向下調整時，母節點要與兩個子節點中較大的一個交換 ，因此要比較一下。

2.這裡下標的計算公式為：左孩子：child = (parent * 2) + 1

右孩子：child = (parent * 2) + 2

3.計算孩子下標時要避免越界，避免將母節點與不屬於堆中的數據比較。

//刪除數據
void Heap_pop(Heap* pphead)
{
    assert(pphead);
    assert(pphead->capacity > 0);      //防止堆為空
    //將頂部數據與尾部數據交換
    swap(&(pphead->head[0]),&( pphead->head[pphead->capacity-1]));
    pphead->capacity--;
    //向下調整
    adjust_down(pphead,0);
}
 
//向下調整
void Adjust_down(int* a, int size, int parent)
{
    assert(a);
    for (int child = parent * 2 + 1; child <= size; child = parent * 2 + 1)
    {
        //默認用左孩紙與母節點比較，如果右孩紙比左孩紙大且不越界則交換
        if (a[child] > a[child + 1] && child + 1 <= size)
            child = child + 1;
        //比較孩紙和母節點
        if (a[child] < a[parent])
        {
            int temp = a[child];
            a[child] = a[parent];
            a[parent] = temp;
        }
        //向下繼續比較
        parent = child;
    }
}

④擴容 || 判空 || 取頂數據 || 銷毀堆

//判斷是否擴容
void Heap_realloc(Heap* pphead)
{
    assert(pphead);
    if (pphead->size == pphead->capacity)
    {
        Heaptype Newsize = (pphead->size == 0) ? 4 : (pphead->size * 2);
        Heaptype* Newhead = (Heaptype*)realloc(pphead->head,sizeof(Heaptype) * Newsize);
        if (Newhead == NULL)
        {
            perror("realloc");
            exit(-1);
        }
        pphead->head = Newhead;
        pphead->size = Newsize;
    }
}
 
//判斷堆是否為空
bool Heap_Empty(Heap* pphead)
{
    if (pphead->capacity)
        return false;
    return true;
}
//取對頂數據
Heaptype Heap_top(Heap* pphead)
{
    return pphead->head[0];
}
//銷毀堆
void Heap_Destory(Heap* pphead)
{
    assert(pphead);
    free(pphead->head);
    pphead->head = NULL;
    pphead->size = 0;
    pphead->capacity = 0;
}

以上就是C語言實現大頂堆的示例代碼的詳細內容，更多關於C語言大頂堆的資料請關註WalkonNet其它相關文章！

推薦閱讀：