二叉堆 堆排序 優先隊列

二叉堆是一个近似完满二叉树的结构，并同时满足堆的性质：
即子结点的键值或索引总是小于（或者大于）它的父节点。

通常堆是通过一维数组来实现的。在起始数组为 0 的情形中：
父节点i的左子节点在位置 (2*i+1);
父节点i的右子节点在位置 (2*i+2);
子节点i的父节点在位置 floor((i-1)/2);

在堆的数据结构中，堆中的最大值总是位于根节点。

堆中定义以下几种操作：
堆调整（heapify）：将堆的末端子结点作调整，维持堆的性质
创建堆（build_heap）：将一个无序数组构造为一个堆。
堆排序（heap_sort）：移除位在第一个数据的根结点，并做堆调整的递归运算

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int parent(int);
int left(int);
int right(int);
void heapify(int [], int, int);
void build_heap(int [], int);
void heap_sort(int [], int);

static void swap(int* a, int* b)
{
    int temp = *b;
    *b = *a;
    *a = temp;
}
 
int parent(int i)
{
    return (int)floor((i - 1) / 2);
}
 
int left(int i)
{
    return (2 * i + 1);
}
 
int right(int i)
{
    return (2 * i + 2);
}
 
/*
 * 堆调整。
 * 以 left(i) 和 right(i) 为根的俩棵子树都已经是堆，
 * 这时A[i]可能小于其子女，所以要进行调整。
 *
 * 调整结果是，以A[i]为根的子树成为一个堆。
 * */
void heapify(int A[], int heap_size, int i)
{
    int l = left(i);
    int r = right(i);
    int largest;
    int temp;
    if (l < heap_size && A[l] > A[i])  {
        largest = l;
    }
    else {
        largest = i;
    }

    if (r < heap_size && A[r] > A[largest])  {
        largest = r;
    }

    if (largest != i) {
        swap(A+i, A+largest);
        heapify(A, heap_size, largest);
    }
}
/* 
 * 将数组A调整为一个堆。
 * 数组A[parent(n-1)]之后的元素都是堆树中的叶子节点。
 * */
void build_heap(int A[], int heap_size)
{
    int i = parent(heap_size-1);
    for (; i >= 0; i--) 
        heapify(A, heap_size, i);
}
/*
 * 每次将堆中最大的元素
 * */
void heap_sort(int A[], int n)
{
    /* 使A[0]称为最大的元素 */
    build_heap(A, n);

    /* 将堆中最后一个叶子节点去掉，还是一个堆，只是堆的大小发生改变。
     * 去掉A[i]后的堆称为新堆，新堆的大小为i。
     * 将新堆的根节点A[0]改为A[i]，这时堆的性质发生改变，需要重新调整。
     * 新堆是A[0...i-1]， A[i]用来保存原堆的根节点。
     * */
    for(int i = n-1; i >= 0; i--) {

        swap(A, A+i);

        heapify(A, i, 0);
    }
}

void print_heap(int A[], int n)
{
    for (int i = 0; i < n; i++) {
        printf("%d ", A[i]);
    }
    printf("\n");
}

#define NUMOF(a) sizeof(a)/sizeof(a[0])
/*輸入資料並做堆積排序*/
int main(int argc, char* argv[])
{
    int A[] = {19, 1, 10, 14, 16, 4, 7, 9, 3, 2, 8, 5, 11};
    heap_sort(A, NUMOF(A));
    print_heap(A, NUMOF(A));
    return 0;
}

高效尤先级队列

主要應用堆的下面兩個操作實現。

 #define MAX_HEAP_NUM 100

#define ERR_HEAP_DATA -1
typedef int HeapDat;
typedef struct heap_tag {
    int size;
    HeapDat data[MAX_HEAP_NUM];
} Heap;

int heap_insert(Heap *heap, HeapDat new_data)
{
    if(heap->size < MAX_HEAP_NUM) {
        HeapDat * heapdata = heap->data;
        int i = heap->size++;

        for (; i>=0 && heapdata[parent(i)] < new_data; i=parent(i))
            heapdata[i] = heapdata[parent(i)];
        heapdata[i] = new_data;

        return 0;
    }
    else 
        return -1;
}


HeapDat heap_extract_max(Heap *heap)
{
    HeapDat max = heap->data[0];
    if (heap->size < 1)
        return ERR_HEAP_DATA;
    heap->size--;
    heap->data[0] = heap->data[heap->size];

    heapify(heap->data, heap->size, 0);
    return max;  
}


int main(int argc, char* argv[])
{
    Heap h = {
        13,
        {19, 1, 10, 14, 16, 4, 7, 9, 3, 2, 8, 5, 11},
    };
    build_heap(h.data, h.size);

    print_heap(h.data, h.size);

    heap_insert(&h, 18);

    print_heap(h.data, h.size);

    heap_extract_max(&h);

    print_heap(h.data, h.size);

    return 0;
}

 另一種建堆的方法:

int _heap_insert(int A[], int n, int new_data, int *heap_size)
{
    if(*heap_size < n) {
        int i = *heap_size;
        for (; i>=0 && A[parent(i)] < new_data; i=parent(i))
            A[i] = A[parent(i)];
        A[i] = new_data;
        *heap_size += 1;
        return 0;
    }
    else 
        return -1;
}


/*
 * 利用heap_insert建堆，跟用上面的方法建的堆不一样。
 * */
void build_heap_2(int A[], int n)
{
    int heap_size=1; 
    do 
        _heap_insert(A, n, A[heap_size], &heap_size);
    while (heap_size < n);
}



/*将A[i] 变为 max(A[i], key); 并重新调整堆
 * */
void heap_increase_key(int A[], int i, int key)
{
    if (key > A[i]) {
        A[i] = key;
        for (; i>=0 && A[parent(i) < key]; i=parent(i)) 
            A[i] = A[parent(i)];
        A[i] = key;
    }
}
/*
 * 将节点A[i]从堆中删除，并重新调整为新的堆。
 * */
int heap_delete(int A[], int heap_size,  int i)
{
    if (i<heap_size) {
        A[i] = A[heap_size-1];
        heapify(A, heap_size, i);
        return 1;
    }
    else
        return 0;
}