大顶堆的实现.md

大顶堆介绍

  大顶堆的基础结构就是完全二叉树, 是一种基础的数据结构, 其特点是根节点是最大值(或最小值); 可以用于实现优先级队列或者堆排序

数组实现的大顶堆

• 根节点处于index为0的位置, 节点的排布方式是广度优先: 第一层index=0, 第二层index = 1, 2...

• 设二叉树节点的下标是n, 那么左孩子的下标是2n+1, 右孩子的下标是2n+2

• 设二叉树节点的下标是n, 那么其父节点的下标是(n-1)/2

基本设计思想

push

• 在数组的末尾插入, 然后与其父节点继续比较, 如果大于其父节点则进行交换, 循环往上直到根节点

• 这样可以保证是一颗完全二叉树

pop操作

• 使用最后一个节点的值替换index=0的位置

• 然后与左右孩子比较, 如果小于其中任意一个与左右孩子中较大的一个进行替换操作

C语言实现

#include <string.h>

typedef struct heap_s heap_t;
int heap_valid = 0;

struct heap_s
{
    int size;
    int capacity;
    int data[0];
};  


heap_t* hp_alloc()
{
    heap_t* hp = (heap_t*)calloc(sizeof(heap_t) + sizeof(int)*8, 1);
    hp->size = 0;
    hp->capacity = 8;
    return hp;
}

int& hp_top(heap_t *hp)
{
    return hp->data[0]; 
}

int hp_pop(heap_t *hp)
{
    if(!hp || hp->size == 0)
    {
        heap_valid = 1;
        return 0;
    }

    int ret = hp->data[0];

    int len = --hp->size;
    hp->data[0] = hp->data[len];
    int *data = hp->data;

    int idx = 0;
    while(1)
    {
        int ls = 2*idx + 1;
        int rs = 2*idx + 2;
        int nt = -1;
        if((ls < len && data[idx] < data[ls]) && (rs < len && data[idx] < data[rs]))
        {
            nt = (data[ls] > data[rs]) ? ls : rs;
        }
        else if(ls < len && data[idx] < data[ls])
        {
            nt = ls; 
        }
        else if(rs < len && data[idx] < data[rs])
        {
            nt = rs;
        }

        if(nt >= 0)
        {
            int tmp = data[idx];
            data[idx] = data[nt]; 
            data[nt] = tmp;
            idx = nt;
        }
        else
            break;  
    }
    return ret;
} 

void hp_push(heap_t **rhp, int t)
{
    if(!rhp || !*rhp)   return;

    heap_t *hp = *rhp;

    if(hp->capacity == hp->size)
    {
        heap_t *nhp = (heap_t*)malloc(sizeof(heap_t) + sizeof(int)*(hp->capacity*2));
        memcpy(nhp, hp, sizeof(hp) + sizeof(int) * hp->capacity);           //?
        nhp->capacity = 2*hp->capacity;
        free(hp);
        hp = nhp;
        *rhp = hp;
    }
    hp->data[hp->size] = t;

    int idx = hp->size++;
    int par = (idx-1)/2;;
    while(idx > 0 && par >= 0 && (hp->data[par] < hp->data[idx]))
    {
        int tmp = hp->data[idx];
        hp->data[idx] = hp->data[par];
        hp->data[par] = tmp;
        idx = par;
        par = (idx-1)/2;
    }
}