程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 最小堆 / 優先隊列（C語言實現）

最小堆 / 優先隊列（C語言實現）

編輯：關於C

最近找實習，復習下數據結構方面的內容。

完全二叉樹有兩種形態，一種是：二叉樹的所有子樹要麼沒有孩子，要麼一定有左孩子。另一種是：二叉樹要麼沒有子樹，要麼一定左右子樹都有。

堆是一種經過排序的完全二叉樹，其中任一非終端節點的數據值均不大於（或不小於）其左孩子和右孩子節點的值。

最大堆和最小堆是二叉堆的兩種形式。

最大堆：根結點的鍵值是所有堆結點鍵值中最大者。

最小堆：根結點的鍵值是所有堆結點鍵值中最小者。

在優先隊列中，元素被賦予優先級。當訪問元素時，具有最高優先級的元素最先刪除。優先隊列具有最高進先出（largest-in，first-out）的行為特征。優先隊列可以用堆來實現。

下面我們用數組來實現一個最小堆。

代碼如下：

MinHeap.h

#ifndef DataStructures_MinHeap_h
#define DataStructures_MinHeap_h

struct MinHeap;
typedef struct MinHeap * MinPriorityQueue;
typedef int ElementType;

// 初始化堆
MinPriorityQueue initialize(int maxElements);

// 銷毀堆
void destroy(MinPriorityQueue pqueue);

// 清空堆中的元素
void makeEmpty(MinPriorityQueue pqueue);

// 插入操作
void insert(ElementType x, MinPriorityQueue pqueue);

// 刪除最小者操作，返回被刪除的堆頂元素
ElementType deleteMin(MinPriorityQueue pqueue);

// 查找最小者（堆頂）
ElementType findMin(MinPriorityQueue pqueue);

// 判斷堆是否為空
int isEmpty(MinPriorityQueue pqueue);

// 判斷堆是否滿
int isFull(MinPriorityQueue pqueue);

// 通過一個數組來建堆，相當於將用數組實現的無序樹轉換為堆序樹
MinPriorityQueue buildHeap_insert(int *arr, int n);
MinPriorityQueue buildHeap_percolate(int *arr, int n);

// 打印堆
void printMinPriorityQueue(MinPriorityQueue pqueue);

#endif

MinHeap.c

#include 
#include 
#include "MinHeap.h"

/* 標記節點，類似於鏈表中的表頭節點
 * 該值必須小於所有最小堆中的元素，設其值為-1
 */
#define SentinelElement -1

/*
 * 使用數組實現堆
 *
 * capacity 數組的最大容量
 * size     數組的長度
 * elements 堆中的元素存放的數組
 */
struct MinHeap
{
    int capacity;
    int size;
    ElementType *elements; // 堆的元素個數為size，實際上用來存儲的數組的長度為size + 1，還包括一個sentinel元素
};

void
PQueueNULLWarning()
{
    printf("Warning: Minimum Priority Queue is NULL");
}

void
outOfSpaceFatalError()
{
    printf("Fatal Error: Out of space");
    abort();
}

MinPriorityQueue
initialize(int maxElements)
{
    MinPriorityQueue pqueue;
    
    if (maxElements <= 0)
    {
        printf("Fail to initialize: maxElements <= 0");
        return NULL;
    }
    
    pqueue = malloc(sizeof(struct MinHeap));
    if (pqueue == NULL)
        outOfSpaceFatalError();
    
    // 數組的第0個元素是個sentinel標記節點，計入數組容量中，但不計入capcaity或size中
    pqueue->size = 0;
    pqueue->capacity = maxElements;
    pqueue->elements = malloc(sizeof(ElementType) * (pqueue->capacity + 1));
    if (pqueue->elements == NULL)
        outOfSpaceFatalError();
    else
        pqueue->elements[0] = SentinelElement;
    
    return pqueue;
}

void
destroy(MinPriorityQueue pqueue)
{
    if (pqueue != NULL)
    {
        // 在GNU99標准中，free(NULL)什麼都不做直接返回，所以不用判斷pqueue->elements是否為NULL
        free(pqueue->elements);
        free(pqueue);
    }
}

void
makeEmpty(MinPriorityQueue pqueue)
{
    if (pqueue != NULL)
        pqueue->size = 0;
    else
        PQueueNULLWarning();
}

/*
 * 插入時，堆中的元素執行下濾操作
 * 刪除時，堆中的元素執行上濾操作
 */

/*
 * 插入的時間復雜度為O(log N)，N為最小堆中的元素個數
 * 實際上，其平均執行時間為O(1)
 */
void
insert(ElementType x, MinPriorityQueue pqueue)
{
    if (pqueue == NULL)
        PQueueNULLWarning();
    
    if (isFull(pqueue))
    {
        printf("Fail to insert: Priority Queue is Full");
        return;
    }
    else
    {
        int i;
        
        // sentinel element在這裡作為elements[0]被比較，是循環的終止條件
        for (i = ++pqueue->size; x < pqueue->elements[i / 2]; i /= 2)
            pqueue->elements[i] = pqueue->elements[i / 2]; // 下濾操作
        pqueue->elements[i] = x;
    }
}

/*
 * 刪除操作的平均時間為O(log N)
 */
ElementType
deleteMin(MinPriorityQueue pqueue)
{
    if (pqueue == NULL)
    {
        PQueueNULLWarning();
        return SentinelElement;
    }
    
    if (isEmpty(pqueue))
    {
        printf("Fail to delete: Priority Queue is Empty");
        return SentinelElement;
    }
    
    int i, child;
    ElementType minElement, lastElement;
    
    // 注意對某個節點進行上濾操作時，要判斷該節點是有兩個兒子還是一個兒子
    minElement = pqueue->elements[1];
    lastElement = pqueue->elements[pqueue->size--];
    for (i = 1; i * 2 <= pqueue->size; i = child)
    {
        child = i * 2;
        
        // 節點i只有一個兒子時必有i * 2 = pqueue->size
        if (child < pqueue->size && pqueue->elements[child] > pqueue->elements[child + 1])
            child++;
        
        if (lastElement < pqueue->elements[child])
            break;
        else
            pqueue->elements[i] = pqueue->elements[child]; // 上濾操作
    }
    pqueue->elements[i] = lastElement;
    
    return minElement; // 返回被刪除的元素
}

/*
 * 執行時間：O(1)
 */
ElementType
findMin(MinPriorityQueue pqueue)
{
    if (pqueue == NULL)
    {
        PQueueNULLWarning();
        return SentinelElement;
    }
    else
        return pqueue->elements[1];
}

int
isEmpty(MinPriorityQueue pqueue)
{
    if (pqueue == NULL)
    {
        PQueueNULLWarning();
        return -1;
    }
    else
        return (pqueue->size == 0);
}

int
isFull(MinPriorityQueue pqueue)
{
    if (pqueue == NULL)
    {
        PQueueNULLWarning();
        return -1;
    }
    else
        return (pqueue->size == pqueue->capacity);
}

void
percolateDown(int *arr, int len, int i)
{
    int n = len - 1;
    int tmp;
    if (i * 2 == n && arr[i] > arr[n]) // 只有左兒子的節點，並且左兒子比本節點的值要小，交換
    {
        tmp = arr[i];
        arr[i] = arr[n];
        arr[n] = tmp;
    }
    else // 有兩個兒子的節點
    {
        if (arr[i * 2] > arr[i * 2 + 1]) // 右兒子較小
        {
            if (arr[i] > arr[i * 2 + 1]) // 如果本節點比右兒子大，交換
            {
                tmp = arr[i];
                arr[i] = arr[i * 2 + 1];
                arr[i * 2 + 1] = tmp;
            }
        }
        else // 左兒子較小
        {
            if (arr[i] > arr[i * 2]) // 如果本節點比左兒子大，交換
            {
                tmp = arr[i];
                arr[i] = arr[i * 2];
                arr[i * 2] = tmp;
            }
        }
    }
}

MinPriorityQueue
buildHeap_percolate(int *arr, int n)
{
    if (arr == NULL)
    {
        printf("Error: Array is NULL");
        return NULL;
    }
    
    MinPriorityQueue pqueue;
    pqueue = malloc(sizeof(struct MinHeap));
    
    if (pqueue == NULL)
        outOfSpaceFatalError();
    ElementType *elements = malloc(sizeof(ElementType) * (n + 1));
    if (elements == NULL)
        outOfSpaceFatalError();
    
    int i;
    for (i = 1; i <= n; i++)
        elements[i] = arr[i - 1];
    elements[0] = SentinelElement;
    
    for (i = n / 2; i > 0; i--)
        percolateDown(elements, n + 1, i);
    
    pqueue->elements = elements;
    pqueue->size = n;
    pqueue->capacity = n * 2;
    
    return pqueue;
}

/*
 * 通過n次插入元素建立堆，由於每次插入的平均執行時間為O(1)，所以建堆平均時間為O(N)
 */
MinPriorityQueue
buildHeap_insert(int *arr, int n)
{
    MinPriorityQueue pqueue;
    
    if (arr == NULL)
    {
        printf("Array is NULL, fail to build heap");
        return NULL;
    }
    
    pqueue = initialize(n * 2);
    for (int i = 0; i < n; i++)
        insert(arr[i], pqueue);
    
    return pqueue;
}

void
printMinPriorityQueue(MinPriorityQueue pqueue)
{
    if (pqueue == NULL)
    {
        PQueueNULLWarning();
        return;
    }
    
    if (pqueue->elements == NULL)
    {
        printf("Fail to print: Elements of priority queue is NULL");
        return;
    }
    
    if (isEmpty(pqueue))
    {
        printf("Empty Prioirty Queue\n");
        return;
    }
    
    printf("Priority Queue\n");
    for (int i = 1; i <= pqueue->size; i++)
        printf("Element[%d] = %d\n", i, pqueue->elements[i]);
    printf("\n");
}

建堆的測試代碼：

#include 
#include 
#include "MinHeap.h"

int main(int argc, const char * argv[])
{
    int a[5] = {5, 4, 3, 2, 1};
    
    MinPriorityQueue pqueue_ins = buildHeap_insert(a, 5);
    MinPriorityQueue pqueue_per = buildHeap_percolate(a, 5);
    printMinPriorityQueue(pqueue_ins);
    printMinPriorityQueue(pqueue_per);
    
    return 0;
}

分別使用插入和下濾兩種方式建堆，所以建立的結果是不同的，輸出如下：

Priority Queue
Element[1] = 1
Element[2] = 2
Element[3] = 4
Element[4] = 5
Element[5] = 3

Priority Queue
Element[1] = 1
Element[2] = 5
Element[3] = 3
Element[4] = 2
Element[5] = 4

最大堆實現類似。