堆,堆排序

简介: 堆,堆排序

堆是一棵完全二叉树,如果其父亲结点的值均比孩子结点大,称大顶堆,反之称为小顶堆,学过数据结构知道用数组表示完全二叉树最为简便,自然而然,我们这里也就用数组来表示堆。

如果数组是从序号1开始,对一棵完全二叉树,下列点如果存在,则对结点i/2是父亲结点,2i和2i+1是左右孩子结点。


1.堆


以建大顶堆为例:

建堆过程可以通过比赛规则来模拟,两两对决决出一个强者,强者再对决…最后在最顶上的就是最强者,这样形成的完全二叉树可以保证每一个父亲结点比其下面的孩子结点要强,只要我们保证所有父亲结点满足上述条件就可以了,而在保证每一个父亲结点是不是最大时,自然要和他下面的孩子结点比,这样由上相下比就是一个向下调整的过程,这个过程会重复多次,不妨先建立一个向下调整的函数

void downadjust(int low,int n){   //向下调整操作 ,low为父亲结点,共n个元素
  int p=2*low;
  while(p<=n){                        
    int temp=p;
    if(p<n&&heap[p]<heap[p+1])temp=p+1;        //找出孩子较大个
    if(heap[p/2]<heap[temp])                  //没有它大,调下去
    {
    swap(heap[p/2],heap[temp]);
    p=temp*2;
    }
    else {
    break;}
  } 
}

现在考虑建堆,完全二叉树的父亲结点共n/2个,只要对这些结点向下调整即可,唯一值得思考是从第一个开始还是从最后一个开始,实际上面的那个向下调整函数是默认下面是大根堆的(思考一下为什么),所以自然是从最后一个父亲结点开始。

void createheap(int n) {                               //建立大根堆 
  for(int i=n/2;i>=1;i--)
  downadjust(i,n);
}

建堆完成后考虑一下删除元素和加入元素,删除最大元素的话,只要把最后一个元素发在堆顶,视堆共n-1,个元素进行一次向下调整即可。

那如何加入元素呢?这里我们直接把元素放在最后一位,对比向下调整,我们来一次向上调整即可。

void upadjust(int n) {     //向上调整操作
   int temp=n/2;
   while(temp>=1){
    if(heap[n]>heap[temp]){
      swap(heap[n],heap[temp]);
    n=temp;
    temp=n/2;
     }
    else{break;} 
   }  
}

2.堆排序


堆排序实际是一种选择排序,正是利用了堆,选择效率比简单选择排序快了许多,我们可以利用大根堆每次把最大元素选出来,放在数列末尾,有点类似于堆删除元素,重复n-1次:

void heapsort(int n){
  createheap(n);
  for(int i=n;i>1;i--)
  {
    swap(heap[1],heap[i]);
    downadjust(1,i-1);
  } 
}

最后附完整的编程代码:


#include <iostream>
#include<algorithm>
using namespace std;
const int maxn=101;
int heap[maxn];
void downadjust(int low,int n){                            //向下调整操作 
  int p=2*low;
  while(p<=n){
    int temp=p;
    if(p<n&&heap[p]<heap[p+1])temp=p+1;           //大根 
    if(heap[p/2]<heap[temp])
    {
    swap(heap[p/2],heap[temp]);
    p=temp*2;
    }
    else {
    break;}
  } 
}
void upadjust(int n) {
   int temp=n/2;
   while(temp>=1){
    if(heap[n]>heap[temp]){
      swap(heap[n],heap[temp]);
    n=temp;
    temp=n/2;
     }
    else{break;} 
   }  
}
void createheap(int n) {                               //建立大根堆 
  for(int i=n/2;i>=1;i--)
  downadjust(i,n);
}
void heapsort(int n){
  createheap(n);
  for(int i=n;i>1;i--)
  {
    swap(heap[1],heap[i]);
    downadjust(1,i-1);
  } 
}
int main(){
  heap[1]=6;
  heap[2]=9;
  heap[3]=1;
  heap[4]=5;
  heap[5]=9;
  heapsort(5);
  for(int i=1;i<=5;i++)
  cout<<heap[i]<<" ";
  return 0;
}
相关文章
|
存储 缓存 算法
数据结构-链表(一)
链表(Linked List)是一种常见的数据结构,用于存储和组织数据。与数组不同,链表的元素(节点)在内存中不必连续存储,而是通过指针链接在一起。 链表由多个节点组成,每个节点包含两部分:数据(存储实际的元素值)和指针(指向下一个节点的引用)。链表的第一个节点称为头节点,最后一个节点称为尾节点,尾节点的指针通常指向空值(null)。
265 1
|
12月前
|
Cloud Native 持续交付 开发者
探索云原生技术:构建高效、灵活的应用架构
【10月更文挑战第6天】 在当今数字化浪潮中,企业面临着日益复杂的业务需求和快速变化的市场环境。为了保持竞争力,他们需要构建高效、灵活且可扩展的应用程序架构。本文将探讨云原生技术如何帮助企业实现这一目标,并分析其核心概念与优势。通过深入剖析云原生技术的各个方面,我们将揭示其在现代应用开发和部署中的重要性,并提供一些实用的建议和最佳实践。
109 2
|
12月前
|
存储 前端开发 JavaScript
从 Web 2.0 到 Web 3.0:前端开发的历史与未来
【10月更文挑战第4天】本文探讨了从 Web 2.0 到 Web 3.0 的前端开发演变过程。Web 2.0 时代,前端开发者从静态网页设计走向复杂交互,技术框架如 jQuery、React 和 Vue 带来了巨大的变革。而 Web 3.0 以区块链技术为核心,带来了去中心化的互联网体验,前端开发者面临与区块链交互、去中心化身份验证、分布式存储等新挑战。文章总结了 Web 2.0 和 Web 3.0 的核心区别,并为开发者提供了如何应对新技术的建议,帮助他们在新时代中掌握技能、设计更安全的用户体验。
354 0
从 Web 2.0 到 Web 3.0:前端开发的历史与未来
|
10月前
|
弹性计算 运维 监控
云服务诊断功能评测报告
云服务诊断功能评测报告
220 3
云服务诊断功能评测报告
|
缓存 自然语言处理 JavaScript
Thinkphp6安装
Thinkphp6安装
205 0
|
JavaScript 前端开发 数据库
Vue之ElementUI实现CUD(增删改)及表单验证
Vue之ElementUI实现CUD(增删改)及表单验证
240 0
wustojc4011计算奖金
wustojc4011计算奖金
85 0
|
存储 搜索推荐 程序员
数据结构项目实战——通讯录
C语言通讯录是一个使用C语言编写的简单程序,用于存储和管理联系人信息。该程序允许用户添加、删除、查找和显示通讯录中的联系人。每个联系人通常包括姓名、电话号码和电子邮件地址等基本信息。程序使用结构体来存储联系人信息,并使用数组或链表等数据结构来组织和管理通讯录。通过命令行界面与用户进行交互,用户可以通过输入命令来执行相应的操作。C语言通讯录程序可以用于个人或小型组织的信息管理,提高联系人信息的管理效率。
243 0
|
Linux 编译器 测试技术
探索Linux设备树:硬件描述与驱动程序的桥梁
探索Linux设备树:硬件描述与驱动程序的桥梁
1222 0
|
XML SQL Oracle
使用mybatis 连接Oracle 数据库 xml 文件中需要注意的问题
使用mybatis 连接Oracle 数据库 xml 文件中需要注意的问题
275 0