堆

　　之前讲的二叉树都是由节点和边构成的，今天我们来用数组表示二叉树．

　　用数组表示的二叉树就不需要指针域了，因为我们可以通过数组的下标来计算节点的左右孩子和父亲节点．

　　如果数组的下标从０开始：求节点ｉ的孩子与父亲

　　　　leftchild[ｉ] = ｉ *  2 + 1;

　　　　rightchild[ｉ] = ｉ *  2 + 2;

　　　　parent[ｉ] = (ｉ - 1) / 2;

　　如果数组的下标从１开始：求节点ｉ的孩子与父亲

　　　　leftchild[ｉ] = ｉ  *  2 ;

　　　　rightchild[ｉ] = ｉ *  2 + １;

　　　　parent[ｉ] = ｉ /  2;

　　用数组实现的二叉树，虽然在增删改查方面速度很快，但内存利用率，灵活性较低．很少有人用数组实现二叉树．

　　接下来讲的堆确是经常用数组来实现的，因为堆是完全二叉树，所以并不会浪费内存．

　　堆有大根堆和小根堆两种．

　　所谓大根堆，就是对任意节点ｉ，ｉ的值大于左右孩子，但对于左右孩子的大小没有要求．根据大根堆的性质，我们可以知道，根节点的值一定是最大的．

　　小根堆与大根堆相反．

　　堆可以用于堆排序和优先级队列

　　下面来实现一个大根堆

　　先看它的结构

typedef struct heap
{
    int * arr;
    int end;
    int size;
} Heap;

　　arr　是一个数组指针,　end是数组中元素的最后一位+1，　size代表数组的大小

　　初始化init

void h_init(Heap * heap, const int size)
{
    heap->arr = (int *)malloc( sizeof(int) * size );
    if ( heap->arr == NULL )
        exit(1);

    heap->end = 0;
    heap->size = size;
}

　　　　首先创建一个数组，end设为０．

　　添加新元素push

void h_push(Heap * heap, const int value)
{
    int pos = heap->end++;
    while ( pos != 0 && value > heap->arr[ (pos - 1) / 2 ] )
        heap->arr[pos] = heap->arr[ ( pos = (pos - 1) / 2 ) ];
    heap->arr[pos] = value;
}

　　在向数组里添加元素时，我们首先要找到添加元素的位置．

　　我们将元素的值与当前pos的父亲比较，如果value大于pos的父亲，把pos的父亲后移到pos，pos变成它的父亲，继续比较．

　　当pos为0或者value 小于pos时，我们找到了value的位置，将value插入

 　　删除首元素pop

　　pop并不是真正的删除首元素，而是将首元素移动到end-1的位置．

　　1)首先将首元素移动到最后一位（end-1）,用tmp保存最后一位元素．从首元素的孩子中找到最大的孩子（max_child），将这个孩子移动到首元素的位置上．

　　2)这时我们将tmp元素与max_child的孩子比较，找到一个最大元素替换max_child．

　　3)如果是tmp替换了max_child，则pop完成，否则将max_child变成max_child的孩子中的最大值，重复上一步．（这里其实是在查找tmp的真正位置）

void h_pop(Heap * heap)
{
    int pos = 0;
    int tmp = heap->arr[--heap->end];
    heap->arr[heap->end] = heap->arr[0];
    if ( heap->arr[pos * 2 + 1] > heap->arr[pos * 2 + 2] )
    {
        heap->arr[pos] = heap->arr[pos * 2 + 1];
        pos = pos * 2 + 1;
    }
    else
    {
        heap->arr[pos] = heap->arr[pos * 2 + 2];
        pos = pos * 2 + 2;
    }
    if ( pos >= heap->end )
        pos = 0;

    while ( pos < heap->end / 2 - 1 )
    {
        if ( heap->arr[pos * 2 + 1] > heap->arr[pos * 2 + 2] )
        {
            if ( tmp > heap->arr[pos * 2 + 1] )
                break;
            else
                heap->arr[pos] = heap->arr[ (pos = pos * 2 + 1) ];
        }
        else
        {
            if ( tmp > heap->arr[pos * 2 + 2] )
                break;
            else
                heap->arr[pos] = heap->arr[ (pos = pos * 2 + 2) ];
        }
    }
    heap->arr[pos] = tmp;
}

　　　如果有STL源码剖析这本书，可以看4.7节的heap，上面的算法描述写的很清楚，我的这些代码都是根据书上的算法描述写的.

　　堆排序

　　由于pop操作并不是真正的删除首元素，而是把首元素放到最后一个位置，所以当我们将堆中所有元素pop一次，元素在数组中将会呈现规律变化（大根堆，递增．小根堆，递减）

　　优先级队列

　　队列我们知道是一种队尾添加元素，队头删除元素的数据结构．

　　优先级队列则是根据权值有着一定顺序的队列．

　　如果我们以堆为容器，通过调用堆的push,pop操作来实现入队出队．end是元素个数，size是数组大小．top的位置是０

　　源码

heap.h

#ifndef _HEAP_H
#define _HEAP_H

typedef struct heap
{
    int * arr;
    int end;
    int size;
} Heap;

void h_init(Heap * heap, const int size);
void h_push(Heap * heap, const int value);
void h_pop(Heap * heap);

#endif //_HEAP_H

heap.c

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

#include "heap.h"

void h_init(Heap * heap, const int size)
{
    heap->arr = (int *)malloc( sizeof(int) * size );
    if ( heap->arr == NULL )
        exit(1);

    heap->end = 0;
    heap->size = size;
}

void h_push(Heap * heap, const int value)
{
    int pos = heap->end++;
    while ( pos != 0 && value > heap->arr[ (pos - 1) / 2 ] )
        heap->arr[pos] = heap->arr[ ( pos = (pos - 1) / 2 ) ];
    heap->arr[pos] = value;
}

void h_pop(Heap * heap)
{
    int pos = 0;
    int tmp = heap->arr[--heap->end];
    heap->arr[heap->end] = heap->arr[0];
    if ( heap->arr[pos * 2 + 1] > heap->arr[pos * 2 + 2] )
    {
        heap->arr[pos] = heap->arr[pos * 2 + 1];
        pos = pos * 2 + 1;
    }
    else
    {
        heap->arr[pos] = heap->arr[pos * 2 + 2];
        pos = pos * 2 + 2;
    }
    if ( pos >= heap->end )
        pos = 0;

    while ( pos < heap->end / 2 - 1 )
    {
        if ( heap->arr[pos * 2 + 1] > heap->arr[pos * 2 + 2] )
        {
            if ( tmp > heap->arr[pos * 2 + 1] )
                break;
            else
                heap->arr[pos] = heap->arr[ (pos = pos * 2 + 1) ];
        }
        else
        {
            if ( tmp > heap->arr[pos * 2 + 2] )
                break;
            else
                heap->arr[pos] = heap->arr[ (pos = pos * 2 + 2) ];
        }
    }
    heap->arr[pos] = tmp;
}

main.c

#include <stdio.h>
#include "heap.h"

int main(void)
{
    int a[9] = { 0, 1, 2, 3, 4, 8, 9, 3, 5 };
    int i;
    Heap heap;

    h_init(&heap, 9);

    for ( i = 0; i < 9; i++ )
        h_push(&heap, a[i]);

    for ( i = 0; i < heap.end; i++ )
        printf("%-10d", heap.arr[i]);
    printf("
");
    h_pop(&heap);
    for ( i = 0; i < heap.end; i++ )
        printf("%-10d", heap.arr[i]);
    printf("
");
    h_pop(&heap);
    for ( i = 0; i < heap.end; i++ )
        printf("%-10d", heap.arr[i]);
    printf("
");
    h_pop(&heap);
    for ( i = 0; i < heap.end; i++ )
        printf("%-10d", heap.arr[i]);
    printf("
");
    h_pop(&heap);
    for ( i = 0; i < heap.end; i++ )
        printf("%-10d", heap.arr[i]);
    printf("
");
    h_pop(&heap);
    for ( i = 0; i < heap.end; i++ )
        printf("%-10d", heap.arr[i]);
    printf("
");
    h_pop(&heap);
    for ( i = 0; i < heap.end; i++ )
        printf("%-10d", heap.arr[i]);
    printf("
");
    h_pop(&heap);
    for ( i = 0; i < heap.end; i++ )
        printf("%-10d", heap.arr[i]);
    printf("
");
    h_pop(&heap);
    for ( i = 0; i < heap.end; i++ )
        printf("%-10d", heap.arr[i]);
    printf("
");
    h_pop(&heap);
    for ( i = 0; i < heap.end; i++ )
        printf("%-10d", heap.arr[i]);
    printf("
");

    printf("heap sort:
");
    for ( i = 0; i < heap.size; i++ )
        printf("%-10d", heap.arr[i]);
    printf("
");
    

    return 0;
}

由于作者水平有限，不足之处请大家指正．