【数据结构与算法】二叉堆

[buckrudy]

二叉堆

二叉堆（英语：binary heap）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。

当父节点的键值总是大于或等于任何一个子节点的键值时为“最大堆”。当父节点的键值总是小于或等于任何一个子节点的键值时为“最小堆”。

二叉堆的存储

二叉堆一般用数组来表示。如果根节点在数组中的位置是1，第n个位置的子节点分别在2n和 2n+1。因此，第1个位置的子节点在2和3，第2个位置的子节点在4和5。以此类推。这种基于1的数组存储方式便于寻找父节点和子节点。

如果存储数组的下标基于0，那么下标为i的节点的子节点是2i + 1与2i + 2；其父节点的下标是floor((i − 1) ∕ 2)。函数floor(x)的功能是“向下取整”，或者说“向下舍入”，即取不大于x的最大整数。比如floor(1.1)、floor(1.9)都返回1。

二叉堆的基本操作

1. 添加操作，将元素添加到堆的末尾，然后向上调整堆。
2. 删除操作，将堆末尾的元素填充到被删除的元素位置，然后向下调整堆。

测试代码

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

#define ARRSIZE(A) (sizeof(A)/sizeof((A)[0]))

typedef struct {
    int *data;
    int maxLen; //容量的最大长度
    int currLen;//堆的最大长度
} BinHeap;

//下沉
void heapify_down(int a[], int start, int end)
{
    int dad = start;
    int son = 2*dad + 1; //left son
    while (son <= end) {
        if (son + 1 <= end && a[son] < a[son + 1])  //找最大的son
            son++;
        if (a[dad] >= a[son])
            return;
        else {
            int temp;
            temp = a[dad];
            a[dad] = a[son];
            a[son] = temp;
            dad = son;
            son = 2 * dad + 1; //left son
        }
    }
}

//上浮
void heapify_up(int a[], int start)
{
    int son = start;
    int dad = (son-1)/2;
    int temp = a[son];

    while (son > 0) {
        if (temp > a[dad]) {
            a[son] = a[dad];
            son = dad;
            dad = (son-1)/2;
        } else
            break;
    }
    a[son] = temp;
}

//构建堆
void heapify_build(int a[], int len)
{
    int i;
    for (i=len/2 - 1; i>=0; i--) {
        heapify_down(a, i, len-1);
    }
}

void binHeap_down(BinHeap *bh, int start)
{
    heapify_down(bh->data, start, bh->currLen);
}

void binHeap_up(BinHeap *bh, int start)
{
    heapify_up(bh->data, start);
}

BinHeap *binHeap_create(int maxLen)
{
    BinHeap *bh;
    bh = calloc(1, sizeof(BinHeap));
    if (!bh)
        return NULL;

    bh->data = malloc(sizeof(int) * maxLen);
    if (!bh->data) {
        free(bh);
        return NULL;
    }

    bh->maxLen = maxLen;
    bh->currLen = 0;

    return bh;
}

void binHeap_init(BinHeap *bh, int a[], int len)
{
    if (!bh)
        return;

    if (bh->maxLen < len)   //不够空间
        return;

    bh->currLen = len;
    memcpy(bh->data, a, sizeof(int)*len);
    heapify_build(bh->data, len);
}

void binHeap_add(BinHeap *bh, int n)
{
    if (bh->currLen < bh->maxLen) {
        bh->data[bh->currLen++] = n;
    }

    heapify_up(bh->data, bh->currLen-1);
}

void binHeap_removeRoot(BinHeap *bh)
{
    if (!bh)
        return;

    if (bh->currLen > 1)
        bh->data[0] = bh->data[--bh->currLen];

    heapify_down(bh->data, 0, bh->currLen);
}

void binHeap_removeValue(BinHeap *bh, int v)
{
    int i;
    if (!bh)
        return;

    for (i=0; i<bh->currLen; i++) {
        if (bh->data[i] == v)
            break;
    }

    if (i < bh->currLen) { //found
        bh->data[i] = bh->data[--bh->currLen];
        heapify_down(bh->data, i, bh->currLen);
    }
}

void binHeap_print(BinHeap *bh)
{
    int i;
    for (i=0; i<bh->currLen; i++)
        printf("%d ", bh->data[i]);
    printf("\n");
}

int main(void)
{
    int a[] = {2, 3, 1, 0, 3, 54, 4, 9, 0, 34};
    BinHeap *bh = binHeap_create(20);
    if (!bh)
        return 1;

    binHeap_init(bh, a, ARRSIZE(a));
    binHeap_print(bh);

    binHeap_add(bh, 5);
    binHeap_print(bh);

    binHeap_removeRoot(bh);
    binHeap_print(bh);

    binHeap_removeValue(bh, 4);
    binHeap_print(bh);
    return 0;
}