首页 > 其他分享 >15.堆

15.堆

时间：2023-06-12 13:44:06浏览次数：39  
标签：arr 15 Heap int heap 节点 size

1.堆的原理

堆（Heap）是一种数据结构，通常用于实现优先队列。堆是一种树形结构，通常由一个完全二叉树构成，因此它只有两个指针，即左子节点和右子节点。堆有两种类型：最大堆（Max Heap）和最小堆（Min Heap）。在最大堆中，父节点的值大于或等于其子节点的值；在最小堆中，父节点的值小于或等于其子节点的值。

堆的主要操作包括：

  1. 插入（Insertion）：将一个元素插入到堆中。在最大堆中，插入元素时将其放入最后一个位置，然后将其与父节点比较并交换位置，直到满足堆的性质。在最小堆中，插入元素时将其放入第一个位置，然后将其与子节点比较并交换位置，直到满足堆的性质。
  2. 删除（Deletion）：从堆中删除一个元素。在最大堆中，删除最后一个元素，然后将最后一个元素与第一个元素交换位置，然后将其与子节点比较并交换位置，直到满足堆的性质。在最小堆中，删除第一个元素，然后将第一个元素与最后一个元素交换位置，然后将其与父节点比较并交换位置，直到满足堆的性质。
  3. 查找（Finding）：查找堆中最大或最小的元素。在最大堆中，查找最后一个元素；在最小堆中，查找第一个元素。

堆是一种高效的数据结构，可以用于实现优先队列、快速排序等算法。

最大堆特点：

1.每个节点最多可以有两个节点
2.根节点的键值是所有堆节点键值中最大者，且每个节点的值都比孩子大
3.除了根节点没有兄弟节点，最后一个左子节点可以没有兄弟节点，其他节点必须有兄弟节点

看图识最大堆： A B 不是堆，C 是最大堆

堆是你见过的最有个性的树！它是用数组表示的树

i的子节点左：2i+1  i的右子节点：2i+2
i的父节点：(i-1)/2

在数组中快速创建堆

  1. 首先我们需要找到最后一个结点的父结点如图(a)，我们找到的结点是87，然后找出该结点的最大子节点与自己比较，若该子节点比自身大，则将两个结点交换。
    图(a)中，87 比左子节点95 小，则交换之。如图(b)所示

2.我们移动到前一个父结点93，如图(c)所示。同理做第一步的比较操作，结果不需要交换。

3.继续移动结点到前一个父结点82，如图(d)所示，82 小于右子节点95，则82 与95 交换，如图(e)所示，82 交换后，其值小于左子节点，不符合最大堆的特点，故需要继续向下调整，如图(f)所示

4.所有节点交换完毕，最大堆构建完成

2.堆的算法实现

堆数据结构的定义

#define DEFAULT_CAPCITY 128
typedef struct _Heap
{
    int *arr; //存储堆元素的数组
    int size; //当前已存储的元素个数
    int capacity; //当前存储的容量
}Heap;

构建最大堆

bool initHeap(Heap& heap, int* original, int size);//将数组用堆的结构存储
static void buildHeap(Heap& heap);//建成最大堆 static阻止外部访问
static void adjustDown(Heap& heap, int index);//向下调整

//初始化堆
bool initHeap(Heap& heap, int* original, int size)
{
	int capacity = DEFAULT_CAPCITY > size ? DEFAULT_CAPCITY : size;

	heap.arr = new int[capacity];
	if (!heap.arr) return false;

	heap.capacity = capacity;
	heap.size = 0;

	//如果存在原始数据则构建堆
	if (size > 0)
	{
		memcpy(heap.arr, original, size * sizeof(int));
		heap.size = size;
		buildHeap(heap);
	}
	return true;
}

/* 从最后一个父节点(size/2-1 的位置)逐个往前调整所有父节点（直到根节
点）,确保每一个父节点都是一个最大堆，最后整体上形成一个最大堆*/
void buildHeap(Heap& heap)
{
	int i;
	for (i = heap.size / 2 - 1; i >= 0; i--)
	{
		adjustDown(heap, i);
	}
}

//将当前的节点和子节点调整成最大堆
void adjustDown(Heap& heap, int index)
{
	int cur = heap.arr[index];//当前待调整的节点
	int parent, child;

	/*判断否存在大于当前节点子节点，如果不存在，则堆本身是平衡的，不需要
	调整；如果存在，则将最大的子节点与之交换，交换后，如果这个子节点还有
	子节点，则要继续按照同样的步骤对这个子节点进行调整*/
	for (parent = index; (parent * 2 + 1) < heap.size; parent = child)
	{
		child = parent * 2 + 1;

		//取两个子节点的最大的节点
		if (((child + 1) < heap.size) && (heap.arr[child] < heap.arr[child + 1]))
		{
			child++;
		}

		//判断最大的节点是否大于当前的父节点
		if (cur >= heap.arr[child])//不大于，则不需要调整，跳出循环
		{
			break;
		}
		else//大于当前的父节点，进行交换，然后从子节点位置继续向下调整
		{
			heap.arr[parent] = heap.arr[child];
			heap.arr[child] = cur;
		}
	}

}

插入新元素

将数字99 插入到上面大顶堆中的过程如下:
1.原始的堆，如图a

对应的数组：{95, 93, 87, 92, 86, 82}
  1. 将新进的元素插入到大顶堆的尾部，如下图b所示:

对应的数组：{95, 93, 87, 92, 86, 82, 99}
  1. 此时最大堆已经被破坏，需要重新调整，因加入的节点比父节点大，则新节点跟父节点调换即可，如图c所示；调整后，新节点如果比新的父节点小，则已经调整到位，如果比新的父节点大，则需要和父节点重新进行交换，如图d，至此，最大堆调整完成。

代码实现：

#include <stdio.h> 
#include <stdlib.h>
#include <string.h>
#define DEFAULT_CAPCITY 128

typedef struct _Heap 
{
    int *arr; //存储堆元素的数组
    int size; //当前已存储的元素个数
    int capacity; //当前存储的容量
}Heap;

bool initHeap(Heap &heap, int *orginal, int size);
bool insert(Heap &heap, int value);
static void buildHeap(Heap &heap);
static void adjustDown(Heap &heap, int index);
static void adjustUp(Heap &heap, int index);

/*初始化堆*/
bool initHeap(Heap &heap, int *orginal, int size)
{
    int capacity = DEFAULT_CAPCITY>size ? DEFAULT_CAPCITY : size;
    heap.arr = new int[capacity];
    if (!heap.arr)   return false;
    heap.capacity = capacity;
    heap.size = 0;
   
    //如果存在原始数据则构建堆
    if(size > 0)
    {
        /*方式一: 直接调整所有元素
        memcpy(heap.arr, orginal, size*sizeof(int));
        heap.size = size;
        //建堆
        buildHeap(heap);
        */
        
        //方式二: 一次插入一个
        for(int i=0; i<size; i++)
        {
            insert(heap, orginal[i]);
        }
    }
    return true;
}

/* 从最后一个父节点(size/2-1 的位置)逐个往前调整所有父节点（直到根节点）,确保每一个父节点都是一个最大堆，最后整体上形成一个最大堆*/
void buildHeap(Heap &heap) 
{
    int i;
    for (i = heap.size / 2 - 1; i >= 0; i--) 
    {
        adjustDown(heap, i);
    }
}

/*将当前的节点和子节点调整成最大堆*/
void adjustDown(Heap &heap, int index)
{
    int cur = heap.arr[index];//当前待调整的节点
    int parent, child;
    /*
    判断否存在大于当前节点子节点，如果不存在，则堆本身是平衡的，不需要调整；
    如果存在，则将最大的子节点与之交换，交换后，如果这个子节点还有子节
    点，则要继续按照同样的步骤对这个子节点进行调整
    */
    for (parent = index; (parent * 2 + 1)<heap.size; parent = child) 
    {
        child = parent * 2 + 1;
        
        //取两个子节点中的最大的节点
        if (((child + 1)<heap.size) && (heap.arr[child]<heap.arr[child +1]))
        {
            child++;
        }
        
        //判断最大的节点是否大于当前的父节点
        if (cur >= heap.arr[child])
        {
            //不大于，则不需要调整，跳出循环
            break;
        }
        else//大于当前的父节点，进行交换，然后从子节点位置继续向下调整
        {
            heap.arr[parent] = heap.arr[child];
            heap.arr[child] = cur;
        }
    }
}

/*将当前的节点和父节点调整成最大堆*/
void adjustUp(Heap &heap, int index)
{
    if(index<0 || index >= heap.size)//大于堆的最大值直接return
    {
        return;
    }
    
    while(index>0)
    {
        int temp = heap.arr[index];
        int parent = (index - 1) / 2;
        if(parent >= 0)//如果索引没有出界就执行想要的操作
        {
            if(temp > heap.arr[parent])
            {
                heap.arr[index] = heap.arr[parent];
                heap.arr[parent] = temp;
                index = parent;
            }
            else//如果已经比父亲小直接结束循环
            {
                break;
            }
        }
        else//越界结束循环
        {
            break;
        }
    }
}

/*最大堆尾部插入节点，同时保证最大堆的特性*/
bool insert(Heap &heap, int value)
{
    if (heap.size == heap.capacity)
    {
        fprintf(stderr, "栈空间耗尽！\n");
        return false;
    }
   
    int index = heap.size;
    heap.arr[heap.size++] = value;
    adjustUp(heap, index);
    return true;
}

int main(void)
{
    Heap hp;
    int origVals[] = { 1, 2, 3, 87, 93, 82, 92, 86, 95 };
    int i = 0;
    if(!initHeap(hp, origVals, sizeof(origVals)/sizeof(origVals[0])))
    {
        fprintf(stderr, "初始化堆失败！\n");
        exit(-1);
    }
    for (i = 0; i<hp.size; i++) 
    {
        printf("the %dth element:%d\n", i, hp.arr[i]);
    }
    insert(hp, 99);
    printf("在堆中插入新的元素99，插入结果:\n");
    for (i = 0; i<hp.size; i++)
    {
        printf("the %dth element:%d\n", i, hp.arr[i]);
    }
    system("pause");
    return 0;
}

参考资料来源：

奇牛学院

标签：arr,15,Heap,int,heap,节点,size
From： https://www.cnblogs.com/codemagiciant/p/17474813.html

相关文章

  • Lua 语言 15 分钟快速入门
    --单行注释--[[  [多行注释]--]]-----------1.变量&控制流----------num=23--数字都是双精度str='aspythonstring'--像Python一样不可变str="aspythonuse"--可以双引号str=[[    像Python的多行注释可用于    表示多行字符串一样 ......
  • Luogu P4824 [USACO15FEB] Censoring S
    [USACO15FEB]CensoringS题面翻译FarmerJohn为他的奶牛们订阅了GoodHooveskeeping杂志，因此他们在谷仓等待挤奶期间，可以有足够的文章可供阅读。不幸的是，最新一期的文章包含一篇关于如何烹制完美牛排的不恰当的文章，FJ不愿让他的奶牛们看到这些内容。FJ已经根据杂志的所有文字，......
  • Xcode 15 beta (15A5160n) - Apple 平台 IDE
    Xcode15beta(15A5160n)-Apple平台IDEIDEforiOS/iPadOS/macOS/watchOS/tvOS/visonOS请访问原文链接：https://sysin.org/blog/apple-xcode-14/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.orgXcode15使您能够为所有Apple平台开发、测试和分发应用程序。......
  • 第15章 模版方法模式（Template Method）
    摘要：TemplateMethod模式是比较简单的设计模式之一，但它却是代码复用的一项基本的技术，在类库中尤其重要。 主要内容1．概述2．TemplateMethod解说3．.NET中的TemplateMethod模式4．适用性及实现要点 概述变化一直以来都是软件设计的永恒话题，在XP编程中提倡拥抱变化，积极应对。如何更好的......
  • CMU15445 (Fall 2020) 数据库系统 Project#2 - B+ Tree 详解（上篇）
    前言考虑到B+树较为复杂，CMU15-445将B+树实验拆成了两部分，这篇博客将介绍Checkpoint#1部分的实现过程，搭配教材《DataBaseSystemConcepts》食用更佳。B+树索引许多查询只涉及文件中的少量记录，例如“找出物理系所有教师”的查询就只涉及教师记录中的一小部分，如果数据库......
  • 9.15 泛型通配符
    demo1“<?>“classMessage<T>{//定义泛型类对象privateTcontent;//泛型属性publicvoidsetContent(Tcontent){this.content=content;}publicTgetContent(){returnthis.content;}}publicclassHelloWorld{......
  • 看看Angular有啥新玩法！手把手教你在Angular15中集成Excel报表插件
    Angular15新特性Angular框架（以下简称“Angular”）作为一款由谷歌开发的Web应用程序框架，其强大的依赖注入系统、可重复使用的模块化开发理念和响应式编程模式等特点让Angular一问世便取得了巨大的关注和流量。截止目前为止，Angular已经迭代了15个版本，而Angular15又有哪些新的亮眼表现......
  • 物理备库在切换为主库时报错ORA-01577—主库已切换为备库
    问题描述：物理备库在切换为主库时报错ORA-01577，如下所示：数据库：oracle11.2.0.4系统架构：rac(2节点)+dg1、异常重现SYS@orcldg>alterdatabasecommittoswitchovertoprimarywithsessionshutdown;alterdatabasecommittoswitchovertoprimarywithsessionshutdown*......
  • 4.15学习总结
    androidstdio中marqueeRepeatLimit无法循环播放 首先，这个控件需要得到焦点，因此来实现循环播放，因此我们要 等我们再次启动虚拟机时，我们能够发现再次点击文字，就能够使控件文字循环播放。 但是这样点击文字循环会让整个页面看起来很傻逼，弄得就好像我们故意跟它显摆似的，......
  • 2023冲刺国赛模拟 15.1
    T1计数首先考虑计数有标号可重叠的方案数，容易发现此时\(x,y\)两维独立，因此考虑其中\(1\)维，设\(f_{i,j}\)表示此时考虑到第\(i\)对左右边界\((x_{i,1},x_{i,2})\)，离散化后的\(x\)坐标形成了\(j\)个点时的方案数，容易发现此时数轴上存在\(j\)个点，以及\(j+1\)个空......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99