小根堆.keywords: 宏 , 堆的自下而上/自上而下的调整

heap.c

/*
 * =========================================================
 *       Filename:  heap.c
 *    Description:  模仿heapq.py创建堆
 *
 * =========================================================
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define SIZE 100
//#define ARRAYLEN(arr) sizeof(arr)/sizeof(arr[0])
#define SWAP( x , y) do{int temp; temp = x; x=y; y=temp;}while(0)
#define PARENT(i) (i - 1)/2
#define LEFT(i) (2*i +1)
#define RIGHT(i) (2*i +2) 

/*---------------------------------------------------
 *  数据集定义 zero-based indexing
 *---------------------------------------------------*/
typedef struct heapq{
    int heap[SIZE];
    int len;
}HeapQ;


/*---------------------------------------------------
 *  方法的定义
 *---------------------------------------------------*/
void initialize(HeapQ *h);
void heappush(HeapQ *h , int item);//自下而上的调整
int heappop(HeapQ *h);//自上而下的调整
HeapQ *heapify(int array[],int n);//不同与heappush的建堆思路
void heapSort(HeapQ *h);
int isempty(HeapQ *h);
void print(HeapQ *h);
void adjust(HeapQ *h , int p);

int main(){
/*     int item;
 *     HeapQ aheap;
 *     initialize(&aheap);
 *     while (scanf("%d",&item) != EOF)
 *         heappush(&aheap , item);
 *     print(&aheap);
 *     heapSort(&aheap);
 */
    int a[]={1,3,5,7,9,2,4,6,8,0};
    HeapQ *h=heapify(a,10);
    heapSort(h);

}

void initialize(HeapQ *h){
    h->len = 0;
}
void heappush(HeapQ *h , int item){
    int p = h->len;//初始化插入点
    h->heap[p] = item;
    while(p>=0 && h->heap[p] < h->heap[PARENT(p)]){//将itempush到堆中,调整item到正确的位置
        SWAP(h->heap[p] , h->heap[PARENT(p)]);
        p = PARENT(p);
    }
    ++h->len;
}
int heappop(HeapQ *h){
    assert(0!= h->len);
    int top = h->heap[0];
    //调整堆
    h->heap[0] = h->heap[h->len -1];//堆尾元素移到堆顶,左右子树均是堆
    --h->len;
    int p =0;//初始化
    adjust(h , p);
    return top;
}
void print(HeapQ *h){
    int i;
    for (i=0 ;i<h->len ;i++)
        printf("%d%s",h->heap[i] ,(i == h->len-1)?"\n":" ");

}
int isempty(HeapQ *h){
    return (h->len == 0)?1:0;
}
void heapSort(HeapQ *h){
    while (!isempty(h)){
        printf("%d ",heappop(h));
    }
    printf("\n");
}
HeapQ *heapify(int array[], int n){
    HeapQ *h;
    h= malloc(sizeof(HeapQ));
    h->len=n;
    int i;
    for (i=0;i<n;i++)
        h->heap[i]=array[i];
    for (i=(h->len)/2 -1;i>=0 ;i--)//i从0开始是不对的 例如 1 2 3 0
        adjust(h , i);
    return h;
}

void adjust(HeapQ *h , int p){//向下局部调整以p为根节点的堆
    int min;
    while (p <= h->len/2){
        min = p;
        if (LEFT(p)< h->len && h->heap[LEFT(p)] <= h->heap[min])//探测left
            min = LEFT(p);
        if (RIGHT(p)< h->len && h->heap[RIGHT(p)] <= h->heap[min])//探测right
            min = RIGHT(p);
        if (min == p)
            break;
        else{
            SWAP(h->heap[p] , h->heap[min]);
            p = min;
        }
    }

}

模仿heapq.py
http://docs.python.org/2/library/heapq

完全二叉树叶节点计算
http://zhidao.baidu.com/link?url=7UzxhpVY5zBXnL91VTI-LNVGbN_Y4jNfqvLdG9hVL9ToMpqaU8UF8LTtC4zEJk1WsgHOmuzR7J4bHhBZjG-uxK