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

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

相关文章
|
1月前
|
存储 算法 Java
散列表的数据结构以及对象在JVM堆中的存储过程
本文介绍了散列表的基本概念及其在JVM中的应用,详细讲解了散列表的结构、对象存储过程、Hashtable的扩容机制及与HashMap的区别。通过实例和图解,帮助读者理解散列表的工作原理和优化策略。
41 1
散列表的数据结构以及对象在JVM堆中的存储过程
|
29天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
55 5
|
28天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
61 1
|
1月前
|
缓存 NoSQL PHP
Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出
本文深入探讨了Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出。文章还介绍了Redis在页面缓存、数据缓存和会话缓存等应用场景中的使用,并强调了缓存数据一致性、过期时间设置、容量控制和安全问题的重要性。
43 5
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
94 16
|
2月前
|
机器学习/深度学习 存储 人工智能
数据结构在实际开发中的广泛应用
【10月更文挑战第20天】数据结构是软件开发的基础,它们贯穿于各种应用场景中,为解决实际问题提供了有力的支持。不同的数据结构具有不同的特点和优势,开发者需要根据具体需求选择合适的数据结构,以实现高效、可靠的程序设计。
128 7
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
218 9
|
1月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
37 1
|
1月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。