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

简介: 数据结构-堆的实现及应用(堆排序和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);
}

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

相关文章
|
24天前
|
存储 算法 Java
散列表的数据结构以及对象在JVM堆中的存储过程
本文介绍了散列表的基本概念及其在JVM中的应用,详细讲解了散列表的结构、对象存储过程、Hashtable的扩容机制及与HashMap的区别。通过实例和图解,帮助读者理解散列表的工作原理和优化策略。
30 1
散列表的数据结构以及对象在JVM堆中的存储过程
|
2月前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
46 1
|
2月前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践,体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案,包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例,帮助读者掌握C语言的基本语法和常用算法,提升编程能力。
70 4
|
26天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
63 16
|
2月前
|
机器学习/深度学习 存储 人工智能
数据结构在实际开发中的广泛应用
【10月更文挑战第20天】数据结构是软件开发的基础,它们贯穿于各种应用场景中,为解决实际问题提供了有力的支持。不同的数据结构具有不同的特点和优势,开发者需要根据具体需求选择合适的数据结构,以实现高效、可靠的程序设计。
75 7
|
2月前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
72 1
|
27天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
123 9
|
18天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
23 1
|
6天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
28 5
|
21天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。