堆的创建、插入、删除、堆排序

堆的概念：
  如果有一个关键码的集合K={K(0),K(1),K(2)……K(n-1)},把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：K(i)<=k(2* i+1)且 K(i)<=k(2* i+2)（K(i)>=k(2* i+1)且 K(i)>=k(2*i+2)）i=0，1，2……则称为小堆(或大堆)。

  说明： 任一结点的关键码均小于(大于)等于它的左右孩子的关键码，位于堆顶结点的关键码最小(最大)，从根结点到每个结点的路径上数组元素组成的序列都是递增的。
  堆存储在下标为0开始的数组中，因此在堆中给定下标为i的结点时：

• 如果i=0，结点i是根结点，没有双亲结点；否则结点i的双亲结点为(i-1)/2。
• 如果2* i+1<=n-1,则结点i的左孩子为2*i+1，否则结点i无左孩子。
• 如果2* i+2<=n-1,则结点i的右孩子为2*i+2,否则结点i无右孩子。

---

堆的创建：

---

堆的插入：
  在已经建成的最小堆的后面插入元素，堆的结构可能被破坏，在向上调整使其满足性质。
堆的删除：
  删除时每次删除堆顶元素
  删除方法：

1. 将堆中最后一个元素代替堆顶元素。
2. 将堆中元素个数减少一个，相当于将堆中最后一个元素删除。
3. 此时堆的结构可能被破坏，在向下调整使其满足性质。

---

堆排序：
  

1. 将堆顶元素与第size-1个元素交换。
2. hp->size–
3. 将其余的元素调整为最小堆
4. 重复1、2、3步hp->size-1次。

---

代码实现：
.h

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

typedef int HDataType;
typedef struct Heap
{
    HDataType *data;
    int size; //有效元素的个数
    int capacity; //容量
}Heap;

//初始化堆
void InitHeap(Heap *hp, int *array, int size);
//创建堆
void CreateHeap(Heap *hp, int *array, int size);
//插入堆
void InsertHeap(Heap *hp, HDataType data);
//删除
void DeleteHeap(Heap *hp);
//打印堆
void PrintHeap(Heap *hp);
//堆排序
void SortHeap(Heap *hp);
//销毁堆
void DestroyHeap(Heap *hp);

.c

#include"Heap.h"


//初始化堆
void InitHeap(Heap *hp, int *array, int size)
{
    assert(hp);
    hp->size = size;
    hp->capacity = 9;
    hp->data = (HDataType *)malloc(hp->capacity*sizeof(HDataType));
    if (hp->data == NULL)
    {
        assert(0);
        return;
    }
    //将array中size*sizeof(HDataType)个字节拷贝到hp->data
    memcpy(hp->data, array, size*sizeof(HDataType));
}

void Swap(HDataType *x, HDataType *y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}
//向下调整
void AdjustDown(Heap *hp, int parent)
{
    //结点i的左孩子为：2*i+1
    int child = (parent << 1) + 1;
    while (child < hp->size)
    {
        //先保证有右孩子,然后获取左后孩子的最小值
        if (child+1 < hp->size && hp->data[child] > hp->data[child + 1])
        {
            child = child + 1;
        }
        //左后孩子的最小值和双亲比较，若双亲大，则与左右孩子的最小值交换
        if (hp->data[parent] > hp->data[child])
        {
            //交换
            Swap(&hp->data[child], &hp->data[parent]);
            parent = child;
            child = (parent << 1) + 1;
        }
        else
        {
            return;
        }
    }
}
//创建堆
void CreateHeap(Heap *hp, int *array, int size)
{
    //从第一个非叶子结点开始调整
    //结点i的双亲为： i-1/2；
    int root = (size - 2) >> 1;
    for (root; root >= 0; root--)
    {
        //向下调整
        AdjustDown(hp, root);
    }
}
//检验容量
void CheckCapacity(Heap *hp)
{
    int newcapacity = 0;
    HDataType *new = NULL;

    assert(hp);

    if (hp->size == hp->capacity)
    {
        newcapacity = hp->capacity * 2;
        new = (HDataType*)realloc(hp->data,newcapacity*sizeof(HDataType));
        if (new == NULL)
        {
            assert(0);
            return ;
        }
        hp->capacity = newcapacity;
        hp->data = new;
    }
}

//向上调整
void AdjustUp(Heap *hp, int parent)
{
    int child = 0;
    assert(hp);
    child = (parent << 1) + 1;
    while (child > 0)
    {
        if (hp->data[parent] > hp->data[child])
        {
            Swap(&hp->data[parent], &hp->data[child]);
            child = parent;
            parent = (child - 1) >> 1;
        }
        else
        {
            return;
        }
    }
}
//插入堆
void InsertHeap(Heap *hp, HDataType data)
{
    assert(hp);
    int root = 0;
    CheckCapacity(hp);
    hp->data[hp->size++] = data;
    root = (hp->size - 2) >> 1;
    //向上调整
    AdjustUp(hp, root);
}


//删除
void DeleteHeap(Heap *hp)
{
    assert(hp);
    //堆顶元素和最后一个元素交换
    Swap(&hp->data[0], &hp->data[hp->size-1]);
    hp->size--;
    //向下调整
    AdjustDown(hp, 0);
}
//打印堆
void PrintHeap(Heap *hp)
{
    int i = 0;
    for (i = 0; i < hp->size; i++)
    {
        printf("%d ", hp->data[i]);
    }
    printf("\n");
}

//堆排序
void SortHeap(Heap *hp)
{
    int i = 0;
    int count = 0;
    assert(hp);
    count = hp->size;
    for (i = 0; i < count - 1; i++)
    {
        //第一个元素与最后一个交换
        Swap(&hp->data[0], &hp->data[hp->size - 1]);
        hp->size--;
        //向下调整成最小堆
        AdjustDown(hp, 0);
    }
    hp->size = count;
}
//销毁堆
void DestroyHeap(Heap *hp)
{
    assert(hp);
    free(hp->data);
    hp->data = NULL;
    hp->capacity = 0;
    hp->size = 0;
}

测试.c

#include"Heap.h"

void Test()
{
    int array[] = { 53, 17, 78, 9, 45, 65, 87, 23, 31 };
    Heap hp;
    //初始化堆
    InitHeap(&hp, array, sizeof(array) / sizeof(array[0]));
    //创建堆
    CreateHeap(&hp, array, sizeof(array) / sizeof(array[0]));
    //插入堆
    InsertHeap(&hp, 4);
    //打印堆
    PrintHeap(&hp);
    //删除堆顶
    DeleteHeap(&hp);
    //打印堆
    PrintHeap(&hp);
    //堆排序
    SortHeap(&hp);
    //打印堆
    PrintHeap(&hp);
    //销毁堆
    DestroyHeap(&hp);
}
int main()
{
    Test();
    system("pause");
    return 0;
}

分析：

运行：