数据结构-堆的实现及应用(堆排序和TOP-K问题)（上）-阿里云开发者社区

一.堆的基本知识点

1.知识点

1.堆的知识点:

堆的知识点
堆的逻辑结构是一颗完全二叉树
堆的物理结构是一个数组
也就是说,给我们是一个数组,可是我们要把它想象成一个完全二叉树来做
通过下标父子结点关系
leftchild = parent * 2 + 1;
rightchild = parent * 2 + 2;
parent = (child - 1) / 2;(child可以是左孩子,也可以是右孩子)

下面我们通过一张图片来更加深刻地理解堆

堆的两个特性
1.结构性:用数组表示的完全二叉树
2.有序性:任意节点的关键字是其子树所有结点的最大值
3.堆的两种分类
最大堆(MaxHeap):也称为大顶堆(最大值)
最小堆(MinHeap):也称为小顶堆(最小值)
3.大堆:要求树中所有的父亲都大于等于孩子
小堆:要求所有的父亲都小于等于孩子
堆只有两种:大堆,小堆,其余的都不是堆,注意有些选择题常考堆的判别
大堆:堆顶数据是最大的
小堆:堆顶数据是最小的

二.堆的实现

1.堆的结构

上面我们说过,堆的物理结构是一个数组,逻辑结构是一个完全二叉树,所以堆的实际结构类似于顺序表,只不过我们的处理方式类似于二叉树

那么我们就可以用顺序表那样的结构来表示堆了

于是我们可以写出这样的代码

typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}HP;
//堆的初始化
void HeapInit(HP* php);
//堆的销毁
void HeapDestroy(HP* php);
//堆的打印
void HeapPrint(HP* php);
//取堆顶数据
HPDataType HeapTop(HP* php);
//判断是否为空
bool HeapEmpty(HP* php);
//返回堆的元素大小
int HeapSize(HP* php);

void HeapInit(HP* php)
{
  assert(php);
  //这里我们将容量初始化为0,当然,初始化为别的一些数值也可以,这里没有强制要求
  php->a = NULL;
  php->size = php->capacity = 0;
}
void HeapDestroy(HP* php)
{
  assert(php);
  free(php->a);
  php->capacity = php->size = 0;
  php->a = NULL;
}
void HeapPrint(HP* php)
{
  int i = 0;
  for (i = 0; i < php->size; i++)
  {
    printf("%d ", php->a[i]);
  }
  printf("\n");
}
HPDataType HeapTop(HP* php)
{
  assert(php);
  assert(php->size > 0);
  return php->a[0];
}
bool HeapEmpty(HP* php)
{
  assert(php);
  return php->size == 0;
}
int HeapSize(HP* php)
{
  assert(php);
  return php->size;
}

剩下的一些常见的接口:

//堆的插入
void HeapPush(HP* php, HPDataType x);
//堆的删除
void HeapPop(HP* php);

在这里,我们要先说明一下:

1.在堆中插入一个数据后,我们不能改变堆的特性,

即:

原来是小堆,插入数据后还是小堆
原来是大堆,插入数据后还是大堆

2.我们的删除操作所要删除的值是堆顶元素.

即数组的第一个元素,

删除操作依然不能改变堆的特性

要想实现堆的插入

首先我们需要先学习一个算法:向上调整算法

2.向上调整算法与堆的插入

假设我们现在有一个小堆(所有的父亲都小于他们所对应的孩子)

我们要插入一个元素

向上调整算法整体思路:

child不断向上跟父亲比,如果比父亲小,跟父亲交换,向上迭代

当该节点调整到父亲小于该节点时,或者该节点调整到数组的首元素位置时调整结束

所以我们可以写出这样的代码

//向上调整算法
//[0,child]区间内向上调整
void AdjustUp(HPDataType* a,int child)
{
  int parent = (child - 1) / 2;
  //终止条件：孩子等于0，大于0就继续调整
  //不要拿父亲作为条件,父亲和孩子都等于0的时候，parent = (0-1)/2还是0，死循环了
  //while(parent>=0)
  while (child > 0)
  {
    //建小堆if(a[child]<a[parent])
    //建大堆if(a[child]>a[parent])
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}

其中,向上调整算法的时间复杂度为O(log2(N)),

最多调整高度次,因为是完全二叉树,所以高度约等于O(log2(N))

实现了向上调整算法之后,我们就可以完成插入了

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, sizeof(HPDataType) * newCapacity);
    if (NULL == tmp)
    {
      perror("malloc fail");
      exit(-1);
    }
    php->a = tmp;
    php->capacity = newCapacity;
  }
  //插入
  php->a[php->size] = x;
  php->size++;
  //向上调整
  AdjustUp(php->a, php->size - 1);
}

2.向下调整算法与堆的删除

假设我们现在有一个小堆

向下调整算法整体思路:

前提:根节点的左子树和右子树都是小堆

child为左右孩子中较小者

如果父亲大于child,交换父亲和child,父亲和孩子向上迭代

于是我们可以写出这样的代码

//向下调整算法(小堆)
//[root,n)区间内向下调整
void AdjustDown(HPDataType* a, int root,int n)
{
  int parent = root;
  int child = 2 * parent + 1;
  while (child < n)
  {
    //建小堆:if(...&& a[child]>a[child+1])
    //建大堆:if(...&& a[child]<a[child+1])
    if (child + 1 < n && a[child] > a[child + 1])
    {
      child++;
    }
    //建小堆:if(a[parent]>a[child])
    //建大堆:if(a[parent]<a[child])
    if (a[parent] > a[child])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = 2 * parent + 1;
    }
    else
    {
      break;
    }
  }
}

实现了向下调整算法的代码后,我们可以写出删除的代码

其中,向下调整算法的时间复杂度也为O(log2(N)),

最多调整高度次,因为是完全二叉树,所以高度约等于O(log2(N))

//删除堆顶元素
void HeapPop(HP* php)
{
  assert(php);
  assert(php->size > 0);
  Swap(&(php->a[0]), &(php->a[php->size - 1]));
  php->size--;
  AdjustDown(php->a, 0, php->size);
}

三.整体代码

Heap.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}HP;
//初始化堆
void HeapInit(HP* php);
//销毁堆
void HeapDestory(HP* php);
//打印堆
void HeapPrint(HP* php);
//插入X继续保持堆形态
void HeapPush(HP* php, HPDataType x);
//删除堆顶元素
void HeapPop(HP* php);
//判断是否为空
bool HeapEmpty(HP* php);
//返回堆顶元素
HPDataType HeapTop(HP* php);
//返回堆的元素大小
int HeapSize(HP* php);

Heap.c

#include "Heap.h"
//初始化堆
void HeapInit(HP* php)
{
  php->a = NULL;
  php->capacity = php->size = 0;
}
//销毁堆
void HeapDestory(HP* php)
{
  free(php);
  php->capacity = php->size = 0;
}
//打印堆
void HeapPrint(HP* php)
{
  int i = 0;
  for (i = 0; i < php->size; i++)
  {
    printf("%d ", php->a[i]);
  }
  printf("\n");
}
void Swap(HPDataType* h1, HPDataType* h2)
{
  HPDataType tmp = *h1;
  *h1 = *h2;
  *h2 = tmp;
}
//向上调整算法
//区间范围:[0,child]
void AdjustUp(HPDataType* a,int child)
{
  int parent = (child - 1) / 2;
  //终止条件：孩子等于0，大于0就继续调整
  //不要拿父亲作为条件,父亲和孩子都等于0的时候，parent = (0-1)/2还是0，死循环了
  //while(parent>=0)
  while (child > 0)
  {
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}
//插入X继续保持堆形态(小堆:父亲小于孩子)
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, sizeof(HPDataType) * newCapacity);
    if (NULL == tmp)
    {
      perror("malloc fail");
      exit(-1);
    }
    php->a = tmp;
    php->capacity = newCapacity;
  }
  php->a[php->size] = x;
  php->size++;
  AdjustUp(php->a, php->size - 1);
}
//向下调整算法(小堆)
//区间范围:[root,n)
void AdjustDown(HPDataType* a, int root,int n)
{
  int parent = root;
  int child = 2 * parent + 1;
  while (child < n)
  {
    if (child + 1 < n && a[child] > a[child + 1])
    {
      child++;
    }
    if (a[parent] > a[child])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = 2 * parent + 1;
    }
    else
    {
      break;
    }
  }
}
//删除堆顶元素
void HeapPop(HP* php)
{
  assert(php);
  assert(php->size > 0);
  Swap(&(php->a[0]), &(php->a[php->size - 1]));
  php->size--;
  AdjustDown(php->a, 0, php->size);
}
//判断是否为空
bool HeapEmpty(HP* php)
{
  return php->size == 0;
}
//返回堆顶元素
HPDataType HeapTop(HP* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  return php->a[0];
}
//返回堆的元素大小
int HeapSize(HP* php)
{
  assert(php);
  return php->size;
}

四.利用回调函数避免对向上和向下调整算法的修改

从上面的讲解中,对于向上调整算法和向下调整算法来说,如果想要实现从小堆到大堆的转换,还需要改一下代码,(尽管只需要改一下比较符号即可),

但是那样的话我们就需要再去实现针对于建大堆的向上调整算法和向下调整算法,

而且还需要根据不同需要去调用不同函数,过于麻烦

所以有什么方法可以避免这种修改吗?

在C语言中,我们可以利用回调函数来完成,对于回调函数来说,大家可以看我的这篇博客

征服C语言指针系列(3)

里面有详细的讲解

1.向上调整算法的修改

void AdjustUp(HPDataType* a, int child, int(*cmp_up)(HPDataType* p1, HPDataType* p2))
{
  int parent = (child - 1) / 2;
  while (child > 0)
  {
    //小堆:if(a[parent]>a[child])
    //也就是说cmp_up(...,...)这个函数返回值为正数,则建的是小堆
    //否则,建的是大堆
    if (cmp_up(&a[parent], &a[child]) > 0)
    {
      Swap(&a[child], &a[parent]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}

2.向下调整算法的修改

void AdjustDown(HPDataType* a, int root,int n, int(*cmp_down)(HPDataType* p1, HPDataType* p2))
{
  int parent = root;
  int child = 2 * parent + 1;
  while (child < n)
  {
    //小堆:if(a[child]>a[child+1])
    //也就是说cmp_down(...,...)这个函数返回值为正数,则建的是小堆
    //否则,建的是大堆
    if (child + 1 < n && cmp_down(&a[child], &a[child + 1]) > 0)
    {
      child++;
    }
    //小堆:if(a[parent]>a[child])
    //也就是说cmp_down(...,...)这个函数返回值为正数,则建的是小堆
    //否则,建的是大堆
    if (cmp_down(&a[parent], &a[child]) > 0)
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = 2 * parent + 1;
    }
    else
    {
      break;
    }
  }
}

函数调用者自行实现两个函数
int cmp_down(HPDataType* p1, HPDataType* p2);
int cmp_up(const HPDataType* p1, const HPDataType* p2);

//使用函数指针来做一个回调函数
cmp_up:向上调整
cmp_down:向下调整
//建小堆(父亲小于孩子)
int cmp_up(const HPDataType* p1, const HPDataType* p2)
{
  return *p1 - *p2;
}
//建大堆
int cmp_up(const HPDataType* p1, const HPDataType* p2)
{
  return *p2 - *p1;
}
//建小堆:父亲小于孩子
int cmp_down(HPDataType* p1, HPDataType* p2)
{
  return *p1 - *p2;
}
//建大堆
int cmp_down(HPDataType* p1, HPDataType* p2)
{
  return *p2 - *p1;
}

3.插入元素和删除元素函数的修改

void HeapPush(HP* php, HPDataType x)
{
  assert(php);
  if (php->capacity == php->size)
  {
    int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
    HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    php->a = tmp;
    php->capacity = newcapacity;
  }
  php->a[php->size] = x;
  php->size++;
  AdjustUp(php->a, php->size - 1, cmp_up);
}

void HeapPop(HP* php)
{
  assert(php);
  assert(php->size > 0);
  Swap(&(php->a[0]), &(php->a[php->size - 1]));
  php->size--;
  AdjustDown(php->a, 0, php->size, cmp_down);
}

经过了上面的修改,我们就可以在不改变代码的情况下,实现大堆或者小堆了

数据结构-堆的实现及应用(堆排序和TOP-K问题)（上）