【Super数据结构】堆结构的建立与调整堆的应用(含堆排序/topK问题)

2024-04-10 08:52

本文主要是介绍【Super数据结构】堆结构的建立与调整堆的应用(含堆排序/topK问题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述

🏠关于此专栏:Super数据结构专栏将使用C/C++语言介绍顺序表、链表、栈、队列等数据结构,每篇博文会使用尽可能多的代码片段+图片的方式。
🚪归属专栏:Super数据结构
🎯每日努力一点点,技术累计看得见

文章目录

  • 二叉树的顺序存储
  • 堆的概念及结构
  • 堆的实现
    • 堆向下调整算法
    • 堆向上调整算法
    • 堆的创建
    • 建堆的时间复杂度
    • 堆的插入
    • 堆的删除
    • 堆的实现代码(含堆的各个常用接口)
  • 堆的应用
    • 堆排序
    • topK问题


二叉树的顺序存储

对于完全二叉树(包含满二叉树),它的结点中,h-1层的结点均是满的,最后一层从左到右连续有结点(不存在结点和空相间的情况)。像这种结构是适合使用二叉树来存储的。

例如下图是一颗完全二叉树,它的高度h为4,它的h-1,即前3层均为满,最后一层从左到右连续有结点。这时,第一层保存在0号下标,第二层保存在1到2号下标,第三层保存在3到6号下标,最后一层保存在7号下标。当要寻找某个结点的左子树根节点时,可以使用i * 2 + 1来得到;例如根节点存储在0号,它的左子树根节点下标等于0 * 2 + 1=1。当要寻找某个结点的右子树根节点时,可以使用i * 2 + 2来得到;例如根节点存储在0号,它的右子树根节点等于0 * 2 + 2=2来得到。如果要寻找某个结点的双亲结点,则可以使用(i - 1) / 2来得到;例如值为7的结点,它的下标为6,可以通过计算(6 - 1) / 2=2得到它的双亲结点位于2号下标。
在这里插入图片描述
那如果是普通的二叉树呢?我们以下图这颗二叉树为例。下图为了保持使用i * 2 + 1找左孩子,i * 2 + 2找右孩子,(i - 1) / 2找双亲节点,不得不浪费大量空间。这颗二叉树存储为数组,如下图所示(其中?表示空出来不适用的位置),这当中存在大量浪费的空间。因此,普通二叉树不适合使用顺序结构存储。
在这里插入图片描述

由上面可知:普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中管理内存的一块区域分段。

堆的概念及结构

如果有一个关键码的集合 K = { k 0 , k 1 , k 2 , … , k n − 1 } K = \{ k_{0},k_{1} ,k_{2} ,…,k_{n-1} \} K={k0k1k2kn1},把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足: k i < = k 2 ∗ i + 1 k_{i}<=k_{2*i+1} ki<=k2i+1 k i < = k 2 ∗ i + 2 k_{i}<=k_{2*i+2} ki<=k2i+2 (其中i=0,1,2…),则称为小堆,也称为最小堆或小根堆。如果满足 k i > = k 2 ∗ i + 1 k_{i}>=k_{2*i+1} ki>=k2i+1 k i > = k 2 ∗ i + 2 k_{i}>=k_{2*i+2} ki>=k2i+2 (其中i=0,1,2…),则称为大堆,也称为最大堆或大根堆。

用大白话描述:小根堆就是所有节点满足:当前节点的值小于其左右孩子的值;大根堆的所有节点满足:当前节点的值大于其左右孩子的值。

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

下面给出一个小堆的示例:下图中的二叉树,所有节点都满足:当前节点的值小于其左右孩子的值。
在这里插入图片描述
下面给出一个大堆的示例:下图中的二叉树,所有节点都满足:当前节点的值大于其左右孩子的值。
在这里插入图片描述
这里的堆,我们使用的是数组存储的,因而我们可以定义一个结构体,其中包含指向动态开辟的数组的首地址的指针、数组有效元素个数、数组容量。

typedef int HPDataType;
typedef struct Heap
{HPDataType* _data;int _size;int _capacity;
}Heap;

堆的实现

堆向下调整算法

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

下图中根节点的左右子树均为一个小堆。如果要将下图这颗树调整为小堆,则我们可以采用向下调整算法。
在这里插入图片描述
向下调整算法思路如下:
1.从某个节点向下调整,则需要使用该节点与其左右孩子进行比较。上图中,从根节点开始调整,则使用数值为9的节点,与它的左右孩子比较(即与值为1和值为4的节点进行比较)。此时要构建的是小堆,则要与数值小的进行交换,让数值小的节点向上移动。(即数值为9的节点与数值为1的节点进行交换)
在这里插入图片描述
2.值为9的节点继续向下调整,此时从它的左右孩子中挑选出最小的,如果如果值为9的节点比值小的节点的数值还要小,则调整结束。但这里值为9的节点比值为3的节点大,故需要继续向下调整。(即值为3的节点与值为9的节点交换)
在这里插入图片描述
3.此时值为9的节点已经到达最后一层,调整结束。

下面给出向下(小堆)调整代码↓↓↓

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//data ---> 指向待调整堆结构数组的起始地址
//parent ---> 向下调整的起始位置
//n ---> 调整的范围
void AdjustDown(HPDataType* data, int parent, int n)
{int child = parent * 2 + 1;while(child < n){if(child + 1 < n && data[child + 1] < data[child]){child++;}if(data[child] < data[parent]){Swap(&data[child], &data[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

下面给出的代码是构建大堆的↓↓↓

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//data ---> 指向待调整堆结构数组的起始地址
//parent ---> 向下调整的起始位置
//n ---> 调整的范围
void AdjustDown(HPDataType* data, int parent, int n)
{int child = parent * 2 + 1;while(child < n){if(child + 1 < n && data[child + 1] > data[child]){child++;}if(data[child] > data[parent]){Swap(&data[child], &data[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

堆向上调整算法

我们通常在给堆插入新元素时,都会插入在它的末尾,新元素插入后就需要使用向上调整算法(在插入新元素前,需要保证当前数组为堆存储结构)。

下图蓝色接变表示原来的堆结构,橙色节点表示新插入的节点。原本的结构是一个小堆。插入新元素后,需要使用向上调整算法,使其变为一个新的小堆。
在这里插入图片描述
向上调整算法的思路(以小堆为例)如下:
1.使用当前节点与其双亲结点比较,如果比其双亲结点小,则与其双亲结点交换(即向上调整)。值为2的结点比其双亲结点(值为4的结点)值要小,故需要与其双亲结点。
在这里插入图片描述
2.经过上一次的向上调整操作后,需要继续与它新的双亲结点比较,如果比它的双亲结点小,则继续向上调整,否则停止调整。值为2的结点比其双亲结点(值为1)的值要大,此时停止调整,算法结束。

下面给出向上的代码↓↓↓

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* data, int child)
{int parent = (child - 1) / 2;while(child > 0){if(data[child] < data[parent]){Swap(&data[child], &data[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

对于大堆的向上调整算法如下所示↓↓↓

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* data, int child)
{int parent = (child - 1) / 2;while(child > 0){if(data[child] > data[parent]){Swap(&data[child], &data[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

堆的创建

堆的存储结构中,本质是一颗使用数组存储的二叉树,起始时其实还不是一个堆。我们需要怎样才能将其构建成一个堆呢?

如果二叉树中只有一个结点,则它也可以是一个堆。因此,我们对于一个存在左右子树,左右子树均只有一个结点的结构,我们可以将其看作是一个左右子树均为堆的结构。此时我们可以使用向下调整算法,将其调整为堆。

上面这段话描述的本质就是:从第一个非叶子结点开始,从该结点到根节点,依次执行向下调整算法。

我们以下面这颗二叉树为例,使用它来构建一个堆(小堆)。我们从第一个非叶子结点,也就是值为8的结点,从该结点及其左侧各个兄弟/堂兄弟结点到根节点,依次指向向下调整。
在这里插入图片描述
8的左右子树只有1个结点,可以将它们看作已经调整好的小堆。由于此时构建的是小堆,从左右孩子中选择小的那个,与8比较发现,比8小。此时需要将结点值为8的与结点值为2的进行交换。
在这里插入图片描述
接下来调整的是值为9的结点,堆它执行向下调整算法。
在这里插入图片描述
此时轮到值为1的结点执行向下调整,此时它的左右子树已经是调整好的小堆结构。但值为1的结点比它的左右孩子结点的值都要小,因此不会发生交换。根节点调整完后,则堆建立完成。

void makeHeap()
{HPDataType data[] = {1,9,8,7,5,6,2};int len = sizeof(data) / sizeof(data[0]);for(int i = (len - 1 - 1) / 2; i >= 0; i++){AdjustDown(data, i, len);}
}

建堆的时间复杂度

由于堆是完全二叉树,满二叉树属于完全二叉树的特例。这里为了计算方便,使用满二叉树来推导计算建堆的时间复杂度。

下图分析了每一层的节点个数及每一层的节点需要向下调整的最大次数。
在这里插入图片描述
建堆的时间复杂度为O(N),推导过程如下图所示。
在这里插入图片描述
上面分析的是向下调整建堆,那如果使用的是向上调整建堆呢?
下图分析了每一层的节点个数及每一层的节点需要向上调整的最大次数。
在这里插入图片描述
建堆的时间复杂度为O(NlogN),推导过程如下图所示。
在这里插入图片描述
由于向上调整建堆的时间复杂度高于向下调整建堆,故我们常规建堆均采用向下调整。

堆的插入

将堆插入至存储堆的数组的末尾,再从末尾执行向上调整算法。

void HeapPush(Heap* php, HPDataType x)
{assert(php);if (php->_size == php->_capacity){HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * php->_capacity * 2);memcpy(tmp, php->_data, sizeof(HPDataType) * php->_size);free(php->_data);php->_data = tmp;php->_capacity *= 2;}php->_data[php->_size] = x;AdjustUp(php->_data, php->_size);php->_size++;
}

堆的删除

删除堆的时候,为了保证堆的结构不被破坏,我们可以执行如下操作:①被删除结点与堆的最后一个结点进行值交换;②将最后一个结点删除(由于最后一个结点是叶子结点,因此不会影响堆结构);③发生值交换的那个结点,由于将最后一个结点的值交换上来,因此无法保证整个结构还是堆;但是能保证该结点的左右子树还是堆,此时我们可以从该结点开始,指向向下调整算法。

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}bool HeapEmpty(Heap* php)
{return php->_size == 0;
}//头删
void HeapPop(Heap* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->_data[0], &php->_data[php->_size - 1]);php->_size--;AdjustDown(php->_data, 0, php->_size);
}

堆的实现代码(含堆的各个常用接口)

头文件Heap.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* _data;int _size;int _capacity;
}Heap;void HeapInit(Heap* php);void HeapDestroy(Heap* php);void HeapPush(Heap* php, HPDataType x);void HeapPop(Heap* php);HPDataType HeapTop(Heap* php);bool HeapEmpty(Heap* php);int HeapSize(Heap* php);

Heap.c源文件

#include "Heap.h"void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustDown(HPDataType* data, int parent, int n)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && data[child + 1] < data[child]){child++;}if (data[child] < data[parent]){Swap(&data[child], &data[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void AdjustUp(HPDataType* data, int child)
{int parent = (child - 1) / 2;while (child > 0){if (data[child] < data[parent]){Swap(&data[child], &data[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}void HeapInit(Heap* php)
{assert(php);php->_data = (HPDataType*)malloc(sizeof(HPDataType) * 2);php->_size = 0;php->_capacity = 2;
}void HeapDestroy(Heap* php)
{assert(php);if (php->_data) free(php->_data);php->_size = php->_capacity = 0;
}void HeapPush(Heap* php, HPDataType x)
{assert(php);if (php->_size == php->_capacity){HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * php->_capacity * 2);memcpy(tmp, php->_data, sizeof(HPDataType) * php->_size);free(php->_data);php->_data = tmp;php->_capacity *= 2;}php->_data[php->_size] = x;AdjustUp(php->_data, php->_size);php->_size++;
}void HeapPop(Heap* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->_data[0], &php->_data[php->_size - 1]);php->_size--;AdjustDown(php->_data, 0, php->_size);
}HPDataType HeapTop(Heap* php)
{assert(!HeapEmpty(php));return php->_data[0];
}bool HeapEmpty(Heap* php)
{assert(php);return php->_size == 0;
}int HeapSize(Heap* php)
{assert(php);return php->_size;
}

堆的应用

堆排序

在进行堆排序前,我们需要先使得数组称为堆结构。在已经是堆结构得数组中(如果是大根堆),则将堆首元素与最后一个元素交换,此时最后一个元素就是最大。
在这里插入图片描述
在这里插入图片描述
此时对除了数组最后一个元素的余下元素,执行向下调整算法,得到第二大的数,即数字8。将它与下标为5的元素交换,此时最后两个元素分别是8和9,是有序的。
在这里插入图片描述
在这里插入图片描述
此时对除了最后两个元素的其他元素做向下调整,此时堆顶是第三大的元素,即数字7。将它与下标为4的元素做交换,此时最后3个元素是有序的。以此类推,不断使用向下调整寻找新的最大的数,将其放置到后面,这样就可以实现堆排序。
在这里插入图片描述
在这里插入图片描述
从上面的分析可知,如果要从小到大排序,需要构建大堆;如果要从大到小排序,需要构建小堆。

下面给出的是堆排序的代码↓↓↓

void HeapSort(int arr[], int len)
{//构建堆for(int i = (len - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, len);}while(len > 0){Swap(&arr[0], &arr[len - 1]);len--;AdjustDown(arr, 0, len);}
}

topK问题

如果需要从100000个数据中选出最大的5个数,我们应该怎么做呢?可能你会想到使用排序算法,再从中选出最大的5个数。但这并不是最优的,这里还有别的思路。

如果我们要选择最大的5个数,可以建立包含5个元素的小堆。因为堆顶存的是当前堆中的最小元素,如果某个元素比整个的堆的最小元素要大,则是截至目前为止的最大的5个最大元素之一;此时将它与堆顶元素元素互换数值,并重新构建小堆。在整个过程中,堆中存的都是截至目前最大的5个数。

下面给出找出最大k个元素的算法代码↓↓↓

void AdjustDown(HPDataType* data, int parent, int n)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && data[child + 1] < data[child]){child++;}if (data[child] < data[parent]){Swap(&data[child], &data[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
int* topKMax(int arr[], int len, int k)
{int* kmax = (int*)malloc(sizeof(int) * k);for(int i = 0; i < k; i++){kmax[i] = arr[i];}//建小堆for(int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(kmax, i, k);}for(int i = k; i < len; i++){if(arr[i] > kmax[0]){kmax[0] = arr[i];AdjustDown(kmax, 0, k);}}return kmax;
}

如果是要求100000个数中最小的5个数,则需要构建大堆。实现代码如下↓↓↓

void AdjustDown(HPDataType* data, int parent, int n)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && data[child + 1] > data[child]){child++;}if (data[child] > data[parent]){Swap(&data[child], &data[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}int* topKMin(int arr[], int len, int k)
{int* kmin = (int*)malloc(sizeof(int) * k);for (int i = 0; i < k; i++){kmin[i] = arr[i];}//建大堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(kmin, i, k);}for (int i = k; i < len; i++){if (arr[i] < kmin[0]){kmin[0] = arr[i];AdjustDown(kmin, 0, k);}}return kmin;
}

如果使用排序算法实现100000个数据中找最大的5个数,则算法时间复杂度至少为O(NlogN)。而采用topk算法后,前k个元素建堆的时间复杂度为O(k),k 到n的元素即使每次都需要向下调整,则时间复杂度为O((n-k)logK),整体的算法复杂度为O(k+(n-k)logk),当k特别小时,此时的算法复杂度趋于O(N)。

🎈欢迎进入Super数据结构专栏,查看更多文章。
如果上述内容有任何问题,欢迎在下方留言区指正b( ̄▽ ̄)d

这篇关于【Super数据结构】堆结构的建立与调整堆的应用(含堆排序/topK问题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/890604

相关文章

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

水位雨量在线监测系统概述及应用介绍

在当今社会,随着科技的飞速发展,各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中,水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术,其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成,形成了一个完整的闭环系统。 数据采集单元:这是系统的“眼睛”,

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

zoj3820(树的直径的应用)

题意:在一颗树上找两个点,使得所有点到选择与其更近的一个点的距离的最大值最小。 思路:如果是选择一个点的话,那么点就是直径的中点。现在考虑两个点的情况,先求树的直径,再把直径最中间的边去掉,再求剩下的两个子树中直径的中点。 代码如下: #include <stdio.h>#include <string.h>#include <algorithm>#include <map>#

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监