数据结构之二叉堆

二叉堆

二叉堆是一棵完全二叉树，什么是完全二叉树呢？简单来说，就是按照层的顺序，对树的节点标号，然后按照层次遍历的顺序来遍历，得到的结果是按照顺序来标号的，不能出现断点，这就是一个完全二叉树。这么说比较抽象，举个例子来说。

1.png

这个二叉树的层次遍历结果是0，1，2，3，4，5，6，7，8.所以是一个完全二叉树。

2.png

这里这棵二叉树进行层次遍历，得到就是0，1，2，3，4，5，6，7，10.编号不是连续的，就不是一棵完全二叉树。

堆就是一棵完全二叉树，不过因为完全二叉树的特性，在实现它的时候往往不是使用链表，而是使用数组来实现，我们可以把上面的二叉树的节点标号与数组的下标对应起来。二叉树的根节点标号从1开始，存储的数组也从下标1开始存储二叉树，一一对应，这种情况下，父节点的数组下标为i，则左子树的数组下标为2i，右子树的下标为2i+1(如果没有超出数组的界限的情况下)

3.png

上图的二叉树将被存储为下面的数组

4.png

在程序里就是如下的访问子节点和父节点。

int heap[10];
//访问第三个节点的父节点
heap[3/2];
//访问第三个节点的左子节点
heap[3*2]
//访问第三个节点的右子节点
heap[3*2+1]

如果是最大堆，那么父节点都要比两个子节点的数值大，相应的最小堆就是父节点比两个子节点都要小。而哨兵的作用就是充当边界检测的角色。如果是最大堆，那么这个值比堆中的数据都要大，如果是最小堆，那么这个值比堆中所有数据都要小。

堆的程序实现

堆的结构定义

typedef int Element;
typedef struct HeapNode
{
    int heapsize; //堆的最大尺寸，也就是数组的最大值
    int size;//堆的当前大小
    Element *data;//数组指针，动态分配数组的大小
};
typedef struct HeapNode* Heap;//堆的指针定义
#define MIN_DATA -20000 //这里实现最小堆，哨兵是最小值，堆中数据的范围是-10000，10000，这个值随需要更改

创建一个heapsize大小的堆

Heap creatHeap(int heapsize)
{
    Heap heap;
    heap=(Heap)malloc(sizeof(struct HeapNode));
    if(heap==NULL)
    {
        printf("内存不足");
        return NULL;
    }
    heap->data=(Element*)malloc(sizeof(Element)*(heapsize+1));
    if(heap->data==NULL)
    {
        printf("内存不足");
        return NULL;
    }
    heap->heapsize=heapsize;
    heap->size=0;
    heap->data[0]=MIN_DATA;
    return heap;
}

判断堆空或者堆满

这个比较简单，因为堆是一个数组，如果size变量为0，表示堆空。如果size变量等于堆数组的最大值，那么就是堆满。

int isFull(Heap heap)
{
    return heap->size==heap->heapsize;
}
int isEmpty(Heap heap)
{
    return heap->size==0;
}

堆的插入操作

堆的插入操作就是首先将size变量加1，当前节点i=size+1,然后访问它的父节点i/2，比较插入的元素和父节点的元素哪个元素小（这里以最小堆为例),如果新插入的元素比较小，那么就将父节点i/2的值赋值到当前节点i。此时将i更新（i=i/2)，然后去比较此时i的节点的父节点（i/2,相当于（size+1）/4）与插入的元素，直到比较到哨兵，因为哨兵是最小值，所以插入的元素会放到数组下标的0的位置。如果比较到其中某个位置时，插入的节点比父节点的大，那么就把插入的节点放到当前位置。以图说话。

5.png

假设有如上的最小堆，堆目前的size是5，如果插入一个元素15，则size加1，相当于把31后面的数组位置空出来，等待插入，然后比较i=6的父节点i/2，此时是16，因为15小于16，所以16就需要下移到数组下标为6的位置了。

6.png

只是将16复制到了数组下标为6的地方，数组下标为3的值没有改变，还是16.然后此时i移动到位置3，比较i=3的父节点i/2，此时是数组的下标1的数据，13<15，说明符合最小堆的定义，父节点小于子节点，所以15应该插入到数组下标为3的地方。插入完成。

7.png

在比如在此时直接插入20元素，size加1等于7，它的父节点的值为15，比20小，所以20直接放到数组下标为7的位置。

插入操作的程序如下：

void insert(Heap heap,Element x)
{
    int i=0;
    if(isFull(heap))
    {
        printf("堆满了");
        return;
    }
    for(i=++heap->size;x<heap->data[i/2];i=i/2) //这里因为有哨兵，所以当i等于0时，是一定会结束循环的，如果不使用哨兵，需要判断一下i为0，否则导致死循环
    {
        heap->data[i]=heap->data[i/2];
    }
    heap->data[i]=x;
}

堆的删除操作

堆的删除操作就是将数组的下标1的数据返回，然后重新构造堆，将size减1，并将最后一个数据找到合理的位置插入。就是从根节点开始（也就是下标1）找到两个子节点的最小值，与最后一个数据比较，如果最后一个数据比两个子节点的最小值还要小的话，那么就把这个数据复制到这两个子节点的父节点；如果最后一个数据比两个子节点的最小值还要大的话，那么就将两个子节点的最小值节点复制到它的父节点，然后以这个子节点作为父节点，重复上述过程，直到找到合适位置。

7.png

假设执行删除操作，13删除，最后一个元素16被取出，size减1，比较13的子节点21和15，15位最小的，那么比较15和16，发现15小，所以将15复制到13的位置。

8.png

此时以数组下标3作为父节点，比较它的两个子节点，但是发现已经没有了，所以把16复制到数组下标3的位置就完成了删除操作。

假设第一次删除13时，它的两个子节点都比16大，那么直接将16复制到数组下标为1的地方，就完成了删除。这就是堆的删除操作的执行过程。

程序代码如下：

Element deleteHeap(Heap heap)
 {
    int child,parent;
    Element x,num;
    if(isEmpty(heap))
    {
        printf("堆空");
        return MIN_DATA;
    }
    x=heap->data[1];//保存要删除的元素，作为返回值
    num=heap->data[heap->size--];//堆的尺寸小1，将这个数值保存以免丢失
    for(parent=1;parent*2<=heap->size;parent=child)
    {
        child=2*parent;
        //寻找两个子节点中最小的一个，&&前面的判断是防止child已经是堆的最后一个数据，加1后超出堆的范围
        if((child+1)<=heap->size&&heap->data[child]>heap->data[child+1])
        {
            child=child+1;
        }
        //比较两个子节点的最小值和要原堆中最后一个元素，如果最后一个元素小，说明找到了插入的位置，结束循环
        if(num<=heap->data[child])
        {
            break;
        }
        else
        {
            heap->data[parent]=heap->data[child];
        }
    }
    heap->data[parent]=num;
    return x;
 }

堆的构建

将一个数组变成最小堆，思路就是从根本一个子树一个子树的逐渐变换，假设数组大小为size，那么它的父节点就是i=size/2，以i为起点，执行与删除操作相同的下滤操作，直到i变成0，就完成了堆的构建，其实就是堆排序的思路。

void perdown(Heap heap,int d)
 {
    int child,parent;
    Element x;
    x=heap->data[d];
    for(parent=d;parent*2<=heap->size;parent=child)
    {
        child=2*parent;
        if((child+1)<=heap->size&&heap->data[child]>heap->data[child+1])
        {
            child=child+1;
        }
        if(x<=heap->data[child])
        {
            break;
        }
        else
        {
            heap->data[parent]=heap->data[child];
        }
    }
    heap->data[parent]=x;
 }
 void buildHeap(Heap heap)
 {
     int i=0;
     for(i=heap->size/2;i>0;i--)
     {
        perdown(heap,i);
     }
 }