堆 最小堆 最大堆 堆排序(小到大,大到小)

简介: 堆 最小堆 最大堆 堆排序(小到大,大到小)

导航


1.了解什么是堆

2.如何创建最小堆,最大堆

3.新增值在堆中如何进行

4.完整的堆排序,升序和降序(两种方式)


——————————————————————————————————————


1.了解什么是堆


树型结构与图型结构的差别:


看是否有回路,无回路的是树型,有回路的是图型



满二叉树可以用数组进行存储,层次遍历顺序存储

设置其中父节点为k,儿子节点(左结点,右节点) 其中左节点 为2*k, 右节点为 2 * k+1

高度为log2^N


其中最典型的应用就是堆(也就是完全二叉树)



完全二叉树:




——————————————————————————————————————


2.如何将堆转化为最小堆,最大堆


有两层的直接用父结点来比较

三层的应该有倒数一层的右边节点开始依次往下



代码如下:(创建最小堆)


//这里用的是数组的方式存储堆
void siftdown(int i)  //输入的是从i点往下找
{
  int t,flag=0;  //flag用来表示无需再进行往下查找 
  //从i位置开始,判断是否有左孩子,并且没有找到最佳位置 
  while(i*2<=n&&flag==0)
  {
  if(h[i]>h[i*2]) //比较父节点与左节点的大小 
    t = i*2;
  else
    t = i;
  if(i*2+1<=n){   //判断是否存在右孩子 
    if(h[t]>h[i*2+1])  //比较上一次父节点与左节点的最小值与右孩子大小 
    t = i*2+1;
  }
  if(t!=i){  //判断得到最小值是否为父节点,是的话flag标志1,不是的话交换,继续往下找 
    swap(t,i);
    i=t;
  }
  else
    flag = 1;
  }
}


创建最大堆:只需要将父节点与左右孩子节点的判大小符号换一下就可以了


——————————————————————————————————————


3.新增值在堆中如何进行


先插入到堆中最后一个位置,在进行与父节点依次比对,找到最合适的位置



整个都用数组保存

代码:


//这里弄得是最小堆 
void siftup(int i)
{
  int i,flag=0;   //flag等于0表示当前子节点比父节点小 
  if(i==1) return;   //如果为根节点直接返回 
  while(i!=1&&flag==0)   
  { 
  if(h[i]<h[i/2])
    swap(i,i/2);
  else
    flag=1;
  i=i/2;    //让子节点等于父节点的位置 
  }
}


——————————————————————————————————————


4.完整的堆排序,升序和降序


输入提示:
14
99 5 36 7 22 17 46 12 2 19 25 28 1 92
升序:
#include <stdio.h>
int h[101]; //用来存放堆的数组
int n;  //存放堆的个数
void swap(int x,int y)
{
  int t;
  t = h[x];
  h[x] = h[y];
  h[y] = t;
} 
void siftdown(int i)
{
  int t,flag=0;  //flag用来表示无需再进行往下查找 
  //从i位置开始,判断是否有左孩子,并且没有找到最佳位置 
  while(i*2<=n&&flag==0)
  {
  if(h[i]>h[i*2]) //比较父节点与左节点的大小 
    t = i*2;
  else
    t = i;
  if(i*2+1<=n){   //判断是否存在右孩子 
    if(h[t]>h[i*2+1])  //比较上一次父节点与左节点的最小值与右孩子大小 
    t = i*2+1;
  }
  if(t!=i){  //判断得到最小值是否为父节点,是的话flag标志1,不是的话交换,继续往下找 
    swap(t,i);
    i=t;
  }
  else
    flag = 1;
  }
}
void create()
{
  int i;
  for(i=n/2;i>=1;i--)
  siftdown(i);
}
//用于返回最小值
int deletemax()
{
  int t;
  t=h[1];
  h[1]=h[n];
  n--;   //删除一位
  siftdown(1);  //进行最小堆
  return t;
}
int main()
{
  int i,num;
  scanf("%d",&num);
  for(i=1;i<=num;i++)
  scanf("%d",&h[i]);
  n = num;
  //建立最小堆
  create();
  //删除顶部元素,接着将最后一个元素放入第一个顶点中,输出删除的元素
  for(i=1;i<=num;i++)
  printf("%d ",deletemax()); 
  return 0;
}



其中deletemax()函数作用是每次返回最小值,并且将最后一个值移入到根节点再次进行最小堆,这样结束时数组中数据已不再是原来的。

若想用这样的来求降序也是可以的,只需要建立最大堆就行了,其余都一样


另一种方式来求解升序和降序


//之前创建的是最大堆 
void headsort()
{
  while(n>1)
  {
  swap(1,n);     //将第一个与最后一个进行交换,此时最后一个点为最大值 
  n--;     //下次建立最大堆不带上最后一个值 
  siftdown(1);  //进行最大堆 
  }
}


求解升序另一种方法完整:


#include <stdio.h>
int h[101]; //用来存放堆的数组
int n;  //存放堆的个数
void swap(int x,int y)
{
  int t;
  t = h[x];
  h[x] = h[y];
  h[y] = t;
} 
void siftdown(int i)
{
  int t,flag=0;  //flag用来表示无需再进行往下查找 
  //从i位置开始,判断是否有左孩子,并且没有找到最佳位置 
  while(i*2<=n&&flag==0)
  {
  if(h[i]<h[i*2]) //比较父节点与左节点的大小 
    t = i*2;
  else
    t = i;
  if(i*2+1<=n){   //判断是否存在右孩子 
    if(h[t]<h[i*2+1])  //比较上一次父节点与左节点的最小值与右孩子大小 
    t = i*2+1;
  }
  if(t!=i){  //判断得到最小值是否为父节点,是的话flag标志1,不是的话交换,继续往下找 
    swap(t,i);
    i=t;
  }
  else
    flag = 1;
  }
}
//开始创建堆 
void create()
{
  int i;
  for(i=n/2;i>=1;i--)
  siftdown(i);
}
//之前创建的是最大堆 
void headsort()
{
  while(n>1)
  {
  swap(1,n);     //将第一个与最后一个进行交换,此时最后一个点为最大值 
  n--;     //下次建立最大堆不带上最后一个值 
  siftdown(1);  //进行最大堆 
  }
}
int main()
{
  int i,num;
  scanf("%d",&num);
  for(i=1;i<=num;i++)
  scanf("%d",&h[i]);
  n = num;
  //建立最小堆
  create();
  headsort(); 
  //删除顶部元素,接着将最后一个元素放入第一个顶点中,输出删除的元素
  for(i=1;i<=num;i++)
  printf("%d ",h[i]); 
  return 0;
}



相关文章
|
10月前
|
网络协议 前端开发 JavaScript
TCP Keepalive 与 HTTP Keep-Alive介绍与区别详解!
TCP Keepalive与HTTP Keep-Alive虽名称相似,但本质不同:前者是TCP层的连接存活探测机制,用于检测“僵死”连接;后者是HTTP层的长连接复用技术,旨在提升性能。二者分属内核与应用层,目标与实现迥异,不可混淆。
1068 10
|
Linux API C++
【C++ 17 新特性 文件管理】探索C++ Filesystem库:文件和目录操作的全面指南(一)
【C++ 17 新特性 文件管理】探索C++ Filesystem库:文件和目录操作的全面指南
3988 3
|
Linux C++ iOS开发
【C++ 17 新特性 文件管理】探索C++ Filesystem库:文件和目录操作的全面指南(二)
【C++ 17 新特性 文件管理】探索C++ Filesystem库:文件和目录操作的全面指南
2540 2
|
SQL 分布式计算 大数据
MaxCompute 聚簇优化推荐简介
在大数据计算中,Shuffle 是资源消耗最大的环节之一。MaxCompute 提供聚簇优化推荐功能,通过调整 Cluster 表结构,有效减少 Shuffle 量,显著提升作业性能并节省计算资源。实际案例显示,该功能可帮助用户每日节省数 PB 的 Shuffle 数据量及数千 CU 的计算成本。
478 0
|
缓存 Unix 应用服务中间件
Nginx,最强单体之一
Nginx是一款高性能的HTTP Web服务器、反向代理、内容缓存及负载均衡器,由伊戈尔·赛索耶夫开发并开源。它采用多进程和I/O多路复用技术,支持高并发和高效处理请求,广泛应用于各大互联网公司。Nginx不仅具备基本的HTTP服务功能,如静态文件处理、反向代理和负载均衡,还支持高级特性如SSL、HTTP/2、动静分离等。其架构设计使其在性能、可靠性、扩展性等方面表现出色,成为Web技术学习和应用的首选工具之一。本文将分两部分介绍Nginx的架构及其原生常用功能。
1280 25
Nginx,最强单体之一
|
消息中间件 前端开发 调度
C++20 协程——你还只是听过?觉得没时间了解,这里可以帮到你。五分钟 从没听过到使用的帮助手册
来源:协程是在C++20 标准中提出的一个新的工具。 它突破传统的程序在cpu中来回切换时需要更新和恢复PCB资源现场的耗时操作(多进程)或者COW(低级调度)操作时间。
777 0
|
消息中间件 Linux
Linux:进程间通信(共享内存详细讲解以及小项目使用和相关指令、消息队列、信号量)
通过上述讲解和代码示例,您可以理解和实现Linux系统中的进程间通信机制,包括共享内存、消息队列和信号量。这些机制在实际开发中非常重要,能够提高系统的并发处理能力和数据通信效率。希望本文能为您的学习和开发提供实用的指导和帮助。
1217 20
|
存储 算法 搜索推荐
图解堆排序(一次弄懂堆结构以及堆排序)
图解堆排序(一次弄懂堆结构以及堆排序)
|
监控 算法 Linux
Linux内核锁机制深度剖析与实践优化####
本文作为一篇技术性文章,深入探讨了Linux操作系统内核中锁机制的工作原理、类型及其在并发控制中的应用,旨在为开发者提供关于如何有效利用这些工具来提升系统性能和稳定性的见解。不同于常规摘要的概述性质,本文将直接通过具体案例分析,展示在不同场景下选择合适的锁策略对于解决竞争条件、死锁问题的重要性,以及如何根据实际需求调整锁的粒度以达到最佳效果,为读者呈现一份实用性强的实践指南。 ####