数据结构——堆的实现和堆排序

数据结构——堆的实现和堆排序

引用

CSDN

1.

https://blog.csdn.net/lrhhappy/article/details/147029631

什么是堆呢？堆其实就是数组，然后我们将数组看成树的结构，创建堆可以是大堆也可以是小堆，有堆就可以用来排序，与冒泡排序相比较效率高很多。

堆的初始化

堆就是数组，所以我们在创建结构体时，需要一个指针指向数组，以及数组容量和有效个数。

typedef int HPDataType;
typedef struct Heap
{
    HPDataType* a;
    int size;
    int capacity;
}Heap;  

typedef int HPDataType 改变int就可以轻易改变数组类型，不需要改多处。

初始化

void HeapInit(Heap* php)
{
    assert(php);
    php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
    if (php->a == NULL)
    {
        perror("malloc fail");
        return;
    }
    php->size = 0;
    php->capacity = 4;
}  

使用malloc函数申请一片空间，使结构体成员指针指向该空间，一开始给四个空间，后面需要容量不够就进行扩容。

堆的插入操作

void HeapPush(Heap* hp, HPDataType x)
{
    assert(hp);
    if (hp->capacity == hp->size)
    {
        HPDataType* tmp = (HPDataType*)realloc(hp->a,sizeof(HPDataType) * hp->capacity * 2);
        if (tmp == NULL)
        {
            perror("realloc fail");
            return;
        }
        hp->a = tmp;
        hp->capacity *= 2;
    }
    hp->a[hp->size] = x;
    hp->size++;
    //向上排
    Sortup(hp->a, hp->size-1);
}  

向堆插入数据，就是向一个数组插入数据，先对数组进行容量判断，如果有效个数等于容量就进行扩容，使用realloc函数进行扩容，向堆中插入数据之后我们需要进行向上调整，就是较大的数据向上调整，在数组中就是后面的数据向前排，树顶的数据要大于左右孩子的数据，这里我们的堆是小堆。

void Sortup(HPDataType* p, int child)
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (p[child] > p[parent])
        {
            Swap(&p[child], &p[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}  

向上调整函数，每当插入一个数据就需要进行调整，这里我们需要知道一个“父母”和“孩子”的关系

从这个图中可以看出左孩子child = parent2，右孩子=parent2+1，在向上调整中只需要知道子节点的位置就可以得到父母节点的位置，而插入数据都是在数组的尾部，所以只需要传最后一个数据的下标（树结构和数组一样从0开始），根据参数来算出父母节点，进行比较，如果子节点大于父母节点就进行交换，交换之后就让child等于parent，再计算新child的父母节点，反之退出循环。进行交换专门写一个函数：

void Swap(HPDataType* a, HPDataType* b)
{
    HPDataType tmp = *a;
    *a = *b;
    *b = tmp;
}  

交换函数传参不可以传值，因为形参是实参的一份临时拷贝，所以在这里需要传址调用。

堆的删除操作

堆的删除操作，应该怎么样删除数据呢？ 直接删除最后一个元素的话，最后一个元素不一定是最小的，但是第一个数据一定的最大的，所以我们删除第一个元素。那么又有一个问题，第一个元素可以直接删除吗？如果直接删除就需要将整个剩下数组往前挪，这样的话效率就太低了。

这里我们可以将第一个数据和最后一个数据进行交换，然后删除最后一个数据，最后来一个向下调整，就可以完成删除操作，并且效率比挪动数据高多了。

void HeapPop(Heap* hp)
{
    assert(hp);
    assert(!HeapEmpty(&hp));
    Swap(&hp->a[0], &hp->a[hp->size-1]);
    hp->size--;
    Sortdown(hp->a, 0, hp->size);
}  

向下调整函数需要三个参数，删除过后的数组，第一个数据的下标，有效数据个数。

void Sortdown(HPDataType* p, int parent, int n)
{
    int child = parent * 2 + 1;
    while ((parent * 2 + 1) < n)
    {
        if (((child + 1) < n) && (p[child] < p[child + 1]))
        {
            child++;
        }
        if (p[parent] < p[child])
        {
            Swap(&p[parent], &p[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}  

拿一组数据1,2,3,4,5,6,7 ，在堆中是以下结构

数组中：

根据删除操作，先交换第一个和最后一个数据，再删除。

接着进入向下调整函数，先对左右孩子进行大小比较，我们先假设左孩子更大，如果有右孩子并且右孩子比左孩子更大就child++，接着就parent和child进行比较，如果child更大就进行交换，反之退出循环

这样我们就完成了我们的删除操作， 效率比一个一个挪动数据快多了。

堆的销毁

void HeapDestory(Heap* hp)
{
    assert(hp);
    free(hp->a);
    hp->a = NULL;
    hp->capacity = 0;
    hp->size = 0;
}  

释放申请的那片空间，结构体成员指针置空，容量和有效数据个数等于0。

堆的应用——堆排序

首先是先建堆，那么建大堆呢还是建小堆呢？这就看是排升序还是排降序。

升序：建大堆

降序：建小堆

建堆的时间复杂度为O(n)。

使用向下调整思想就可以实现堆排序

void HeapSort(int* a, int n)
{
    //向下建大堆---最大的数据在顶
    for (int i = (n-2)/2; i >= 0; i--)
    {
        Sortdown(a, i, n);
    }
    //向上建大堆
    /*for (int i = 0; i < n; i++)
    {
        Sortup(a, i);
    }*/
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        end--;
        Sortdown(a, 0, end);
    }
}
test()
{
    int a[12] = { 8,7,6,3,5,4,9,1,2,0,8,9 };
    HeapSort(a,12);
    for (int i = 0; i < 12; i++)
    {
        printf("%d ", a[i]);
    }
}  

建堆有两种方法，一个是向下建堆，一个是向上建堆，在数据很多时向下建堆比向上建堆更快一些 ，反之向上建堆更快。交换第一个和最后一个，再向下调整，这里和堆删除操作差不多。

运行结果：