热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

【数据结构】堆的实现(简单易懂,超级详细!!!)

目录1、堆的概念及结构概念规律2、堆的实现2.1结构设计2.2接口实现2.3初始化2.4堆的向下调整算法主要思想涉及问题代码实现2.5建堆思想代码实现

目录

1、堆的概念及结构

概念

规律 

2、堆的实现

2.1结构设计

2.2接口实现

2.3 初始化 

2.4堆的向下调整算法

主要思想

涉及问题

代码实现

2.5建堆

思想

代码实现

建堆的时间复杂度

2.6 堆的向上调整算法

主要思想

​涉及问题

代码实现

2.7 插入 

2.8删除堆顶元素

2.9取堆顶元素

2.10 堆的大小

2.11 堆是否为空

2.12 堆销毁

3、源代码

1. 头文件

2. 接口函数

3.测试文件




1、堆的概念及结构


概念

        堆(heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:


性质1:堆中某个结点的值总是不大于或不小于其父结点的值;
性质2:堆总是一棵完全二叉树。


        将根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆。

        如下,小堆父亲节点总是小于孩子节点,所以小堆的根节点一定是最小的。而大堆父亲节点总是大于孩子节点,所以大堆的根节点一定是最大的


规律 

        既然堆的逻辑结构是完全二叉树,那么它就同样具有完全二叉树的性质。


         对于完全二叉树,若从上至下、从左至右编号,以根节点为0开始,则编号为i的节点,其左孩子节点编号为2i+1,右孩子节点编号为2i+2,父亲节点为 (i-1) / 2。 这个规律非常重要!!!


         我们来验证一下:


        一棵节点个数为N的完全二叉树,其高度为 h = log 2 (N+1)   ,(2为底数)。


        推导过程如下:

        我们来做个简单的题目:


1.下列关键字序列为堆的是?()

A 100,60 ,70 ,50 ,32 ,65
B 60 ,76 ,65 ,50 ,32 ,100
C 65 ,100,70 ,32 ,50 ,60
D 70 ,65 ,100,32 ,50 ,60
E 32 ,50 ,100,70 ,65 ,60
F 50 ,100, 70,65 ,60 ,32


        在这里,由于堆的存储结构数组,且堆是完全二叉树,可以直接如下图A,把后面的移过去,每一层放置可以放的最大节点个数,直到数组内元素放置完。很容易就可以看出 A 是堆。


2、堆的实现


2.1结构设计

        如下,用数组存储数据,实际存储结构是数组。

typedef int HeapDataType;typedef struct Heap
{HeapDataType* a;int size; //已有数据个数int capacity; //容量
}HP;

2.2接口实现


2.3 初始化 

        如下,非常简单,就不多说了。

//初始化
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}

2.4堆的向下调整算法


主要思想

        现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提:左右子树必须是同一种堆,才能调整


int array[] = {27,15,19,18,28,34,65,49,25,37};


        我们可以通过画图构建这棵树,然后走一遍向下调整的过程,如下图 (a)是构建的完全二叉树,从(b)中明显看出,根节点的左右子树都是小堆,所以可以调整。而横线下方就是调整的详细步骤,每一次,根节点都和左右孩子节点中,较小的那个孩子交换 :


涉及问题


        在此过程中,我们要明确几个问题:
1、如何找到孩子节点?

2、如何判断该孩子节点是否存在?(比如值为 28 的节点,不存在右孩子)

3、边界条件?什么时候停止调整?


        由于堆逻辑结构是一颗完全二叉树,所以要利用上面完全二叉树的规律。

        1、  我们用 parent、leftchild、rightchild,分别代表父亲节点、左右孩子节点的下标(物理结构是数组)。 根据规律得:  leftchild = parent * 2 + 1 ,rightchild = parent * 2 + 2 。并且任一节点 i ,其父亲节点 parent = (i-1)/2

        2、由于数组一共有n个元素,其下标最大是 n-1,所以孩子节点的下标只要 小于 n ,就是存在的。

        3、首先,由于其子树是小堆,所以如果调整到某个节点,其父亲节点比孩子节点都小,就不需要调整了,那么已经构建成功(相当于做了一半就成功)。

        其次,就是调整到最后一步的情况,如下。每次调整,改变的都是代表父亲节点孩子节点 下标的那几个变量。父亲节点的值和孩子节点的值交换之后,下一轮调整 父亲节点的下标就变成了上一轮孩子节点的下标孩子节点的下标变成当前 父亲节点的孩子节点中 小的那个的下标。所以孩子节点 > n,那么就代表调整到了最下面一层,不需要再调整了。

          小结论: 如上图,向下调整算法前提是,根节点的左右子树都是大堆或者都是小堆。然后调整之后的结果是,根节点调整到了下方,整棵树成了一个堆。    但是,我们深入思考一下,如果现在调整的根节点,也是某个节点的孩子节点呢? 那么,就能得到,向下调整算法实际上是调整的某一个节点 A,要这个节点的左右子树都是同种堆,调整之后,以原 A 位置的节点为根节点的树是一个堆。

        如下,从左边标红的地方开始向下调整,不用管其父亲节点等只需要知道标红节点的左右子树都是同种堆即可,然后调整得到右半边结果。(很重要,要理解!!!这是理解建堆算法的前提!!!


代码实现

        如下,由于一次只需要交换一个父亲节点和一个孩子节点,且孩子节点存储时是相邻的,所以用child 先表示 左孩子节点下标,然后循环内部和右孩子节点比较,如果右孩子节点存在且其值小于左孩子节点的值,那么child++++之后的child节点表示的是右孩子节点。 然后比较,需要交换就交换parent 和 child 代表的下标的内容,然后parent 和 child 更新;如果不需要交换,那么就是调整好的,break。

        传入三个参数,依次是指向堆的数据的指针,堆的长度,根节点。

void Swap(HeapDataType* a, HeapDataType* b)
{int c = *a;*a = *b;*b = c;
}//向下调整
void AdjustDown(HeapDataType* a, int n, int parent)
{assert(a);int child = parent * 2 + 1; // 这里和链表里的长链表、短链表有异曲同工之妙,只不过这里只需要用到大的孩子while (child a[child + 1] && child + 1 size ,不可以=,因为数据个数是比下标大1{child++;}if (a[parent] > a[child]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else // 父亲小于等于孩子,所以已经完成调整,直接break{break;}}
}

2.5建堆


思想

        建堆写在这里,相信聪明的你已经猜到,需要使用向下调整算法,要使用这个算法,就要有一个前提 —— 要调整的节点,左右子树都是同种堆。

        如下,方法一,我们从根节点开始调整,但是本身这棵树就是乱序的,没有哪一个节点的子树能保证是堆,更不要说是同种堆了。所以这种方法根本不可行。

        既然从一棵树的上方开始调整不行,那么我们就从下方开始调整,如方法二。但是这里开始调整的起始位置也很有讲究,是从最后一个节点开始吗? 显然不是,从上面的小规律已经得知,向下调整算法实际上是调整了开始的那个节点,而一棵树最后一个节点是叶子节点,叶子节点根本没有孩子节点,更不要说子树了,没有什么好调整的。所以我们要从有孩子节点的 节点开始调整。

        如下方法2 ,从圈出来的步骤 1 到步骤5 。步骤一中,值为37 的节点,左右子树都是堆,可以调整这个值为37的节点。后面依次也是。最后完成调整,建队成功。


代码实现

        如下,传入三个参数,依次是堆指针,数组,数组长度。  首先把开辟堆内存储数据的空间,然后把数组的值复制进去,然后建堆。

void HeapCreat(HP* php, HeapDataType* a, int len)
{assert(php);assert(a);php->a = (HeapDataType*)malloc(sizeof(HeapDataType) * len);if (php->a == NULL){perror("malloc fail::");exit(-1);}memcpy(php->a, a, sizeof(HeapDataType) * len);php->size = php->capacity = len;for (int i = (len - 1 - 1) / 2;i >= 0;i--){AdjustDown(php->a, php->size, i);}}

建堆的时间复杂度

        由于建堆是从倒数第二行开始,所以 是 h-1 层开始计数。最终结果约等于 N 。所以向下调整算法建堆的时间复杂度是O(N)。


2.6 堆的向上调整算法


主要思想

        向上调整算法是从节点 n 开始,调整 节点n 到根节点 之间的路径上的节点(任一节点到根节点之间的路径唯一)。其结果是,将这条路径上,最大或者最小的节点,放到根节点位置。这个算法的前提是:这条路径,除了节点n,其余节点要满足堆的特性,即有序。(自己用文字总结的,可能存在一些不标准的地方,欢迎指正!)

        比如,现有一个数组,其逻辑结构是一个堆,新加一个元素再数组末尾,并且使用向上调整算法使其保持逻辑结构依然是一个堆。


int array[] = {12,15,19,18,28,34,65,49,25,37};

新增 6 放在数组末尾。


          如下,不难看出,向上调整算法的路径是: 6 — 28 — 15 — 12 。而除了6 所代表的节点,这条路径上,从上往下看,是升序的,所以最后结果是,这条路径上的最小值到了根节点的位置。


涉及问题

         这里的问题无非和向下调整算法类似。找父亲节点也不难,最主要的就是边界条件,即如何确定循环结束条件。通过上面的图片可以看出, child = 0 就结束了,所以控制条件如下面代码所示。


代码实现

        如下,传入两个参数,一个是指向堆的数据的指针,一个是要调整的孩子节点。

void AdjustUp(HeapDataType* a, int child)
{assert(a);int parent = (child - 1) / 2;while (child > 0){if (a[parent] }

         此外,也可以通过向上调整算法建堆,当然了,用该算法,要从上面往下建堆,而不是从下往上。 从根节点到最后一个节点依次调整,这样就可以保证,每一条路径,除了n节点之前的节点,都是有序的。如下:

         核心代码如下,前面开辟空间和复制什么的,和向下调整建堆一摸一样,就不写了。

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

2.7 插入 

        由于存储结构是数组,所以插入要考虑是否扩容。

void HeapPush(HP* php, HeapDataType x)
{assert(php);//扩容if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HeapDataType* ptr = (HeapDataType*)realloc(php->a, sizeof(HeapDataType) * newcapacity);if (ptr == NULL){perror("realloc fali::");exit(-1);}php->a = ptr;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

2.8删除堆顶元素

        把堆尾元素放到堆顶元素,然后去除堆尾元素(这里直接size--),再向下调整即可。因为原本就是一个堆,现在堆顶元素变了,所以直接向下调整。

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

2.9取堆顶元素

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

2.10 堆的大小

int HeapSize(HP* php)
{assert(php);return php->size;
}

2.11 堆是否为空

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

2.12 堆销毁

//销毁
void HeapDestory(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}

3、源代码


1. 头文件

#pragma once
#include
#include
#include
#include
#include
#includetypedef int HeapDataType;typedef struct Heap
{HeapDataType* a;int size; //已有数据个数int capacity; //容量
}HP;//初始化
void HeapInit(HP* php);
//插入
void HeapPush(HP* php, HeapDataType x);
//删除堆顶元素
void HeapPop(HP* php);
//销毁
void HeapDestory(HP* php);
//向上调整
void AdjustUp(HeapDataType* a, int child);
void AdjustDown(HeapDataType* a, int n);
//建堆
void HeapCreat(HP* php, HeapDataType* a, int len);
//打印
void Print(HP* php);
//取堆顶元素
HeapDataType HeapTop(HP* php);
int HeapSize(HP* php);
bool HeapEmpty(HP* php);

2. 接口函数

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"//初始化
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}//插入
void HeapPush(HP* php, HeapDataType x)
{assert(php);//扩容if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HeapDataType* ptr = (HeapDataType*)realloc(php->a, sizeof(HeapDataType) * newcapacity);if (ptr == NULL){perror("realloc fali::");exit(-1);}php->a = ptr;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}//销毁
void HeapDestory(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}void Swap(HeapDataType* a, HeapDataType* b)
{int c = *a;*a = *b;*b = c;
}//向上调整
void AdjustUp(HeapDataType* a, int child)
{assert(a);int parent = (child - 1) / 2;while (child > 0){if (a[parent] }void Print(HP* php)
{for (int i = 0;i size;i++){printf("%d ", php->a[i]);}printf("\n");
}//向下调整
void AdjustDown(HeapDataType* a, int n, int parent)
{assert(a);int child = parent * 2 + 1; // 这里和链表里的长链表、短链表有异曲同工之妙,只不过这里只需要用到大的孩子while (child a[child + 1] && child + 1 size ,不可以=,因为数据个数是比下标大1{child++;}if (a[parent] > a[child]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapPop(HP* php)
{assert(php);assert(php->size > 0);php->a[0] = php->a[php->size - 1];php->size--;AdjustDown(php->a, php->size, 0);
}HeapDataType HeapTop(HP* php)
{assert(php);assert(!php->a);return php->a[0];
}void HeapCreat(HP* php, HeapDataType* a, int len)
{assert(php);assert(a);php->a = (HeapDataType*)malloc(sizeof(HeapDataType) * len);if (php->a == NULL){perror("malloc fail::");exit(-1);}memcpy(php->a, a, sizeof(HeapDataType) * len);php->size = php->capacity = len;for (int i = (len - 1 - 1) / 2;i >= 0;i--){AdjustDown(php->a, php->size, i);}}int HeapSize(HP* php)
{assert(php);return php->size;
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

3.测试文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"Test1()
{int arr[] = { 10,78,99,45,67,45,0,77,34 };HP hp;HeapInit(&hp);for (int i = 0;i }Test2()
{int arr[] = { 10,78,99,45,67,45,0,77,34 };HP hp;HeapInit(&hp);HeapCreat(&hp, arr, sizeof(arr) / sizeof(arr[0]));Print(&hp);
}int main()
{//Test1();//Test2();return 0;
}


推荐阅读
  • 本文详细介绍了Java编程语言中的核心概念和常见面试问题,包括集合类、数据结构、线程处理、Java虚拟机(JVM)、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题,帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • 1:有如下一段程序:packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • 在金融和会计领域,准确无误地填写票据和结算凭证至关重要。这些文件不仅是支付结算和现金收付的重要依据,还直接关系到交易的安全性和准确性。本文介绍了一种使用C语言实现小写金额转换为大写金额的方法,确保数据的标准化和规范化。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • C++实现经典排序算法
    本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出,帮助读者全面了解这些排序方法的特点。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 数据管理权威指南:《DAMA-DMBOK2 数据管理知识体系》
    本书提供了全面的数据管理职能、术语和最佳实践方法的标准行业解释,构建了数据管理的总体框架,为数据管理的发展奠定了坚实的理论基础。适合各类数据管理专业人士和相关领域的从业人员。 ... [详细]
  • 本文详细介绍了 Dockerfile 的编写方法及其在网络配置中的应用,涵盖基础指令、镜像构建与发布流程,并深入探讨了 Docker 的默认网络、容器互联及自定义网络的实现。 ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • 深入解析Android自定义View面试题
    本文探讨了Android Launcher开发中自定义View的重要性,并通过一道经典的面试题,帮助开发者更好地理解自定义View的实现细节。文章不仅涵盖了基础知识,还提供了实际操作建议。 ... [详细]
  • PyCharm下载与安装指南
    本文详细介绍如何从官方渠道下载并安装PyCharm集成开发环境(IDE),涵盖Windows、macOS和Linux系统,同时提供详细的安装步骤及配置建议。 ... [详细]
  • 本文详细介绍如何使用Python进行配置文件的读写操作,涵盖常见的配置文件格式(如INI、JSON、TOML和YAML),并提供具体的代码示例。 ... [详细]
  • 本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
  • CentOS7源码编译安装MySQL5.6
    2019独角兽企业重金招聘Python工程师标准一、先在cmake官网下个最新的cmake源码包cmake官网:https:www.cmake.org如此时最新 ... [详细]
author-avatar
津pig
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有