首页 > 其他分享 >【数据结构】堆

【数据结构】堆

时间：2024-09-17 13:50:44浏览次数：14  
标签：php parent int HPDataType child 数据结构 size

二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，

需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
在这里插入图片描述

堆的概念及结构

如果有一个关键码的集合K = { k0，k1 ，k2 ，…，kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：ki <=k2*i+1 且 ki <=k2*i+2 ( ki >=k2*i+1 且 ki >=k2*i+2 ) i = 0，1，2…，则称为小堆(或大堆)。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
在这里插入图片描述

堆的实现

堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。

我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

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

在这里插入图片描述

//堆向上调整算法
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//while (parent >= 0)
	while(child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//堆向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 假设法，选出左右孩子中小的那个孩子
		if (child+1 < n && a[child + 1] < a[child])
		{
			++child;
		}

		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

请注意：
父子存储位置的下标规律：

leftchild=parent*2+1;
rightchild=parent*2+2;
parent=(parent-1)/2;

堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。

根节点左右子树不是堆，我们怎么调整呢？
这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

int a[] = {1,5,3,8,7,6};

在这里插入图片描述

void HPInitArray(HP* php, HPDataType* a, int n)
{
	assert(php);
	
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->capacity = php->size = n;

	// 向上调整，建堆 O(N*logN)
	//for (int i = 1; i < php->size; i++)
	//{
	//	AdjustUp(php->a, i);
	//}

	// 向下调整，建堆 O(N)
	for (int i = (php->size-1 - 1)/2; i >= 0; i--)
	{
		AdjustDown(php->a, php->size, i);
	}
}

建堆时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
在这里插入图片描述

堆的插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。
在这里插入图片描述

void HPPush(HP* php, HPDataType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}

	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size-1);
}

堆的删除

删除堆是删除堆顶的数据，将堆顶的数据跟最后一个数据交换，然后删除数组最后一个数据，再进行向下调整算法。

在这里插入图片描述

void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}

堆的代码实现

Heap.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>
#include<time.h>

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

void HPInit(HP* php);
void HPInitArray(HP* php, HPDataType* a, int n);

void HPDestroy(HP* php);
// 插入后保持数据是堆
void HPPush(HP* php, HPDataType x);
HPDataType HPTop(HP* php);

// 删除堆顶的数据
void HPPop(HP* php);

bool HPEmpty(HP* php);

void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);
void Swap(HPDataType* px, HPDataType* py);

Heap.c

#include"Heap.h"

void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

void HPInitArray(HP* php, HPDataType* a, int n)
{
	assert(php);
	
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->capacity = php->size = n;

	// 向上调整，建堆 O(N*logN)
	//for (int i = 1; i < php->size; i++)
	//{
	//	AdjustUp(php->a, i);
	//}

	// 向下调整，建堆 O(N)
	for (int i = (php->size-1 - 1)/2; i >= 0; i--)
	{
		AdjustDown(php->a, php->size, i);
	}
}

void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}

void Swap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

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

// 时间复杂度：
void HPPush(HP* php, HPDataType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}

	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size-1);
}

HPDataType HPTop(HP* php)
{
	assert(php);

	return php->a[0];
}

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 假设法，选出左右孩子中小的那个孩子
		if (child+1 < n && a[child + 1] < a[child])
		{
			++child;
		}

		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

// 时间复杂度：logN
void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}


bool HPEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

标签：php,parent,int,HPDataType,child,数据结构,size
From： https://blog.csdn.net/Sakura_ding/article/details/142313569

相关文章

  • 数据结构-树和二叉树
      树和二叉树 1.树的概念   树tree     是n(n>=0)个节点的有限集    在任意的一个非空树中       (1)有且仅有一个特定的被称为根(root)的节点       (2)当n>1时,其余的节点可分为m(m>0)个互不相交的有限......
  • C#数据结构与算法实战入门指南
    前言在编程领域，数据结构与算法是构建高效、可靠和可扩展软件系统的基石。它们对于提升程序性能、优化资源利用以及解决复杂问题具有至关重要的作用。今天大姚分享一些非常不错的C#数据结构与算法实战教程，希望可以帮助到有需要的小伙伴。C#经典十大排序算法主要讲解C#经典......
  • 数据结构与算法（四）线性表的抽象数据类型描述
    一、回顾    上一篇我们讲到了线性表的定义，讲到了所谓抽象数据类型就是把数据类型和操作捆版在一起。那么我们接下来分析一下，线性表应该有什么样的相关操作呢？。    从一个例子来看一看，回到我们上一篇开学参加升旗仪式的例子：    老师把同学们按照规......
  • Java-数据结构-二叉树-习题(二) (´▽`)ﾉ
    文本目录：❄️一、习题一(分层遍历)：   ▶ 思路：    ▶代码：❄️二、习题二(二叉树的最近公共祖先)：    ▶ 思路： ▶代码： ❄️三、习题三(从前序和中序遍历序列中构造二叉树)：     ▶ 思路：  ▶代码：❄️四、习题四(从中序和后序遍历序列中构造二......
  • C++数据结构-二叉树的三种遍历方法（进阶篇）
    1.遍历简介：树作为非线性数据结构，在我们取出数据时就需要设计遍历，所谓遍历，就是按照一定的规则性，将数据结构中的所有数据全部依次访问，而二叉树本身并不具有天然的全局次序，故为实现遍历，需通过在各节点与其孩子之间约定某种局部次序，间接地定义某种全局次序，这便是我们常规定的先序......
  • C++数据结构-二叉树的存储方法（基础篇）
    1.简介根据前文的介绍，我们知道了二叉树的性值，其就是一种每一个结点中只允许拥有左右孩子（或为空）的树，这种数据结构在我们的实际设计中非常常用，如前文提到的STL中的set集合，其底层就是一颗标准的红黑树（二叉树的一种），我们这里以创建一颗二叉树并实现通过特定的插入顺序和读取顺序达......
  • 数据库索引分类以及底层数据结构
    数据库索引的分类和底层数据结构直接决定了它在不同场景下的性能和适用性。以下是数据库索引的主要分类及其底层数据结构的详细分析：一、数据库索引的分类1.主键索引（PrimaryKeyIndex）分类：唯一性索引的一种特殊形式。特点：对主键列创建的索引，保证唯一性且不能为空。底层结构：B......
  • 【数据结构和算法实践-树-LeetCode113-路径总和Ⅱ】
    数据结构和算法实践-树-LeetCode113-路径总和Ⅱ题目MyThought代码示例JAVA-8题目给你二叉树的根节点root和一个整数目标和targetSum，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。叶子节点是指没有子节点的节点输入：root=[5,4,8,11,null,13......
  • 数据结构之快速排序、堆排序概念与实现举例
    1、快速排序快速排序是一种高效的排序算法，采用分治法策略。它的基本思想是：通过一个划分操作，将待排序的数组分为两个（尽可能）均等的子数组，使得左侧子数组中的所有元素都不大于右侧子数组中的任何元素，然后对这两个子数组分别进行快速排序，整个排序过程可以递归进行，以此达到整个......
  • 数据结构之希尔排序
    1、希尔排序希尔排序是一种基于插入排序的算法，通过比较相距一定间隔的元素来工作，然后逐渐减少这个间隔，直到它变为1，此时算法退化为简单插入排序，但此时，大部分元素已经是基本有序的，所以最后的插入排序效率很高。2、希尔排序说明与举例希尔排序是一种基于插入排序的高效排序......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99