数据结构-堆结构与堆排序思想-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构-堆结构与堆排序思想。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

heap.h

#pragma once
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <errno.h>
#include <stdlib.h>
//数组实现堆
typedef int HPDataType;
typedef struct Heap
{
   HPDataType* a;
   int size;
   int capacity;
}HP;
void HeapInit(HP* php);//初始化堆
void HeapDestroy(HP* php);//销毁堆
void HeapPush(HP* php, HPDataType x);//插入数据
void HeapPop(HP* php);//删除数据
HPDataType HeapTop(HP* php);//取堆顶元素
bool HeapEmpty(HP* php);
void HeapSort(int* a, int n);//堆排序

heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "heap.h"

void HeapInit(HP* php)
{
   assert(php);
   php->a = NULL;
   php->size = 0;
   php->capacity = 0;
}
void HeapDestroy(HP* php)
{
   free(php->a);
   php->a = NULL;
   php->size = 0;
   php->capacity = 0;
}
void AdjustUp(HPDataType* x,int child)
{
   int parent = (child-1)/2;
   while (child>0)
   {
       //建小堆
       if (x[parent] > x[child])
       {
           HPDataType tmp = x[parent];
           x[parent] = x[child];
           x[child] = tmp;
           child = parent;
           parent = (child - 1) / 2;
       }
       else
       {
           break;
       }
   }
}
void HeapPush(HP* php, HPDataType x)
{
   //插入数据不是会对整个堆产生影响，而是对要插入的位置的祖先有影响
   //（设是小根堆）若插入的数据比父节点大，则直接插入
   //若插入的数据比父节点小，则不能直接插入
   //此时引入向上调整算法:
   //如果插入的数据比小，则和父节点交换位置
   //交换完之后再和此结点的父节点比较，如果还小，则继续调换
   //最坏的情况就是要调整到根
   assert(php);
   if (php->size == php->capacity)
   {
       int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
       HPDataType* tmp = (HPDataType*)realloc(php->a,newCapacity * sizeof(HPDataType));
       if (tmp == NULL)
       {
           perror("realloc fail::");
           return;
       }
       php->a = tmp;
       php->capacity = newCapacity;
   }
   php->a[php->size] = x;
   php->size++;
   AdjustUp(php->a, php->size - 1);
}

//向下调整算法的前提，根的左右子树必须是一个小堆/大堆
//向下调整时，如果是小堆，则根只和小儿子比较即可，如果是大堆则只和大儿子比较即可
void AdjustDown(HPDataType * a,int n, int parent)
{
   //假设认为左孩子小
   int child = 2 * parent + 1;
   while (child<n)
   {
       //找到真正小的那个孩子
       if (child + 1 < n && a[child] > a[child + 1])
       {
           HPDataType tmp = a[child];
           a[child] = a[child + 1];
           a[child + 1] = tmp;
       }
       if (a[child] < a[parent])
       {
           HPDataType tmp = a[child];
           a[child] = a[parent];
           a[parent] = tmp;
           parent = child;
           child = 2 * parent + 1;
       }
       else {
           break;
       }
   }
}
void HeapPop(HP* php)//删除堆顶元素
{
   //不能只单独删除数组首个元素，因为后面的父子关系全变了，不能保证其还是一个堆
   //方法1：挪动覆盖删除堆顶元素，重新建堆(太麻烦，不考虑)
   //
   //方法2：收尾数据交换，再删除，再调堆 √
//收尾交换后，删除堆顶就会很简单，直接size--就可以了。然后此时原先的堆尾元素此时在堆顶
   //中间的数据都没变，即堆的左右子树都还是一个堆
   //此时只有堆顶元素不符合逻辑
//所以此时可以单独对堆顶元素进行向下调整
   HPDataType tmp = php->a[0];
   php->a[0] = php->a[php->size - 1];
   php->a[php->size - 1] = tmp;
   php->size--;
   AdjustDown(php->a, php->size, 0);
}

HPDataType HeapTop(HP* php)
{
   assert(php);
   assert(!HeapEmpty(php));
   return php->a[0];
}

bool HeapEmpty(HP* php)
{
   assert(php);
   return php->size == 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "heap.h"

//topK问题：优质筛选（店面的排名）
   //10000个数，找出最大的前10个数
   //解决思路：建立大堆，然后pop9次

//堆排序
   //建小堆排降序
   //思路：将小堆收尾交换，即将最小的放在最后的位置
   //然后，最后一个数据，不看做堆里面的
   //此时，向下调整，就可以选出次小的数

   //建大堆排升序



void HeapSort(int *a, int n)
{

   //首先建堆：
//所以采用向上调整的方式：像上调整的条件-》上面的结构必须是堆

   for (int i = 1; i < n; i++)
   {
       AdjustUp(a,i);
   }

   //这里给出向下调整建堆的方法：
   // 向下调整虽然较向上调整算法难理解，但是其时间复杂度为o(N)级别，而向上调整算法为o(N*logN)级别。
   // 注意事项：
   // 1.因为向下调整的前提是要其后面的数据是一个堆,所以不能上来就直接向下调整，而是采用倒着调整的方式
   // 2.叶子结点不需要处理
   // 3.从倒数第一个非叶子结点，也就是最后一个结点的父亲开始调整
   // for(int i = (n-1-1)/2; i >= 0; i --)
   // {
   // AdjustDown(a,n,i);
   // }
   //
   //升序：建大堆
   // 【大堆，选出了最大的，收尾交换，最大的放在最后的位置。把最后一个数据，不看做堆里面的，向下调整就可以选出次大的数据】
   //降序：建小堆
   //【小堆，选出了最小的，收尾交换，最小的放在最后的位置。把最后一个数据，不看做堆里面的，向下调整就可以选出次小的数据】

   //小堆：
   int end = n - 1;
   while (end > 0)
   {
       //不断将顶端的数据和末端数据交换，更新堆
       HPDataType tmp = a[0];
       a[0] = a[end];
       a[end] = tmp;
       AdjustDown(a, end , 0);
       end--;
   }
}
int main()
{
   HP hp;
   HeapInit(&hp);
   int a[] = { 1,3,7,2,6,19 };
   for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
   {
       HeapPush(&hp, a[i]);
   }
   HeapSort(hp.a, hp.size);
   return 0;
}文章来源地址https://www.toymoban.com/news/detail-604650.html