C++实现堆排序实例介绍

目录
  • 概述：
  • 思路：
  • 代码：

概述：

堆排序是利用构建“堆”的方法确定具有最大值的数据元素，并把该元素与最后位置上的元素交换。可将任意一个由n个数据元素构成的序列按照（a1，a2，...，an），按照从左到右的顺序按层排列构成一棵与该序列对应的完全二叉树。

一棵完全二叉树是一个堆，当且仅当完全二叉树的每棵子树的根值ai≥其左子树的根值a2i，同时ai≥其右子树的根值a 2i+1 (1<i<n/2)。

实现堆排序需要实现两个问题：

如何由无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？

思路：

堆排序算法思想：

1、从最后一个非叶子节点逐步到树根，对每个子树进行调整堆。

2、重复n-1次如下处理：将堆的根与最后一个叶子交换，除最后一个叶子之外剩余部分再调整为堆。

调整堆算法思想：

1、将树根与其左右子树根值最大者交换；（大顶堆）

2、对交换后的左（或右）子树重复过程1，直到左（或右）子树为堆。

时间复杂度：O(nlogn)

代码：

调整堆算法：

void HeapAdjust(int *array,int i,int length){	//调整堆
	int leftChild=2*i+1;		//定义左右孩子
	int rightChild=2*i+2;
	int max=i;		//初始化，假设左右孩子的双亲节点就是最大值
	if(leftChild<length&&array[leftChild]>array[max]){
		max=leftChild;
	}
	if(rightChild<length&&array[rightChild]>array[max]){
		max=rightChild;
	}
	if(max!=i){		//若最大值不是双亲节点，则交换值
		swap(array[max],array[i]);
		HeapAdjust(array,max,length);	//递归，使其子树也为堆
	}
}

堆排序算法：

void HeapSort(int *array,int length){	//堆排序
	for(int i=length/2-1;i>=0;i--){		//从最后一个非叶子节点开始向上遍历，建立堆
		HeapAdjust(array,i,length);
	}
	for(int j=length-1;j>0;j--){		//调整堆 ，此处不需要j=0
		swap(array[0],array[j]);
		HeapAdjust(array,0,j);		//因为每交换一次之后，就把最大值拿出(不再参与调整堆)，第三个参数应该写j而不是length
		Print(array,length);
	}
}

完整代码：

//堆排序
#include <iostream>
using namespace std;
void Print(int array[],int length){	//每执行一次打印一次序列
	for(int i=0;i<length;i++){
		cout<<array[i]<<" ";
	}
	cout<<endl;
}
void HeapAdjust(int *array,int i,int length){	//调整堆
	int leftChild=2*i+1;		//定义左右孩子
	int rightChild=2*i+2;
	int max=i;		//初始化，假设左右孩子的双亲节点就是最大值
	if(leftChild<length&&array[leftChild]>array[max]){
		max=leftChild;
	}
	if(rightChild<length&&array[rightChild]>array[max]){
		max=rightChild;
	}
	if(max!=i){		//若最大值不是双亲节点，则交换值
		swap(array[max],array[i]);
		HeapAdjust(array,max,length);	//递归，使其子树也为堆
	}
}
void HeapSort(int *array,int length){	//堆排序
	for(int i=length/2-1;i>=0;i--){		//从最后一个非叶子节点开始向上遍历，建立堆
		HeapAdjust(array,i,length);
	}
	for(int j=length-1;j>0;j--){		//调整堆 ，此处不需要j=0
		swap(array[0],array[j]);
		HeapAdjust(array,0,j);		//因为每交换一次之后，就把最大值拿出(不再参与调整堆)，第三个参数应该写j而不是length
		Print(array,length);
	}
}
int main(){
	int array[]={49,38,65,97,76,13,27,49};
	int length=sizeof(array)/sizeof(*array);
	Print(array,length);			//先打印原始序列
	HeapSort(array,length);
	return 0;
}

运行示例：

第一行是原始序列，第二到八行分别是经过7次调整堆所得到的序列。

到此这篇关于C++实现堆排序实例介绍的文章就介绍到这了,更多相关C++堆排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++ 数据结构 堆排序的实现

    C++ 数据结构 堆排序的实现

    堆排序(heapsort)是一种比较快速的排序方式,它的时间复杂度为O(nlgn),并且堆排序具有空间原址性,任何时候只需要有限的空间来存储临时数据.我将用c++实现一个堆来简单分析一下. 堆排序的基本思想为: 1.升序排列,保持大堆:降序排列,保持小堆: 2.建立堆之后,将堆顶数据与堆中最后一个数据交换,堆大小减一,然后向下调整:直到堆中只剩下一个有效值: 下面我将简单分析一下: 第一步建立堆: 1.我用vector顺序表表示数组: 2.用仿函数实现大小堆随时切换,实现代码复用: 3.实现向下

  • 解读堆排序算法及用C++实现基于最大堆的堆排序示例

    解读堆排序算法及用C++实现基于最大堆的堆排序示例

    1.堆排序定义 n个关键字序列Kl,K2,-,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质): (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤   ) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字. [例]关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1

  • C++堆排序算法实例详解

    本文实例讲述了C++堆排序算法.分享给大家供大家参考,具体如下: 堆中元素的排列方式分为两种:max-heap或min-heap,前者每个节点的key都大于等于孩子节点的key,后者每个节点的key都小于等于孩子节点的key. 由于堆可以看成一个完全二叉树,可以使用连续空间的array来模拟完全二叉树,简单原始的实现如下: #include<iostream> int heapsize=0;//全局变量记录堆的大小 void heapSort(int array[],int n){ void

  • C++实现堆排序示例

    目录 堆的实现 Heap.h 堆的管理及接口 Heap.c 堆各个接口功能的实现 test.c测试 堆的实现 Heap.h 堆的管理及接口 #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }Heap; //堆的向下调整算法 void Adj

  • C++堆排序算法的实现方法

    C++堆排序算法的实现方法

    本文实例讲述了C++实现堆排序算法的方法,相信对于大家学习数据结构与算法会起到一定的帮助作用.具体内容如下: 首先,由于堆排序算法说起来比较长,所以在这里单独讲一下.堆排序是一种树形选择排序方法,它的特点是:在排序过程中,将L[n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子节点之间的内在关系,在当前无序区中选择关键字最大(或最小)的元素. 一.堆的定义 堆的定义如下:n个关键字序列L[n]成为堆,当且仅当该序列满足: ①L(i) <= L(2i)且L(i) <= L(2

  • C++实现堆排序实例介绍

    C++实现堆排序实例介绍

    目录 概述: 思路: 代码: 概述: 堆排序是利用构建"堆"的方法确定具有最大值的数据元素,并把该元素与最后位置上的元素交换.可将任意一个由n个数据元素构成的序列按照(a1,a2,...,an),按照从左到右的顺序按层排列构成一棵与该序列对应的完全二叉树. 一棵完全二叉树是一个堆,当且仅当完全二叉树的每棵子树的根值ai≥其左子树的根值a2i,同时ai≥其右子树的根值a 2i+1 (1<i<n/2). 实现堆排序需要实现两个问题: 如何由无序序列建成一个堆?如何在输出堆顶元素

  • 通过PHP简单实例介绍文件上传

    php文件上传的简单例子,获取文件名称.类型.大小等相关信息,完成文件的上传,供大家学习参考. 1.上传文件的代码: code <?php //判断临时文件存放路径是否包含用户上传的文件 if(is_uploaded_file($_FILES["uploadfile"]["tmp_name"])){ //为了更高效,将信息存放在变量中 $upfile=$_FILES["uploadfile"];//用一个数组类型的字符串存放上传文件的信息

  • BootStrap响应式导航条实例介绍

    BootStrap响应式导航条实例介绍

    Bootstrap,来自 Twitter,是目前最受欢迎的前端框架.Bootstrap 是基于 HTML.CSS.JAVASCRIPT 的,它简洁灵活,使得 Web 开发更加快捷.响应式导航条就是可以在不同的设备下查看不同的效果. 下面给大家分享代码: <header role="banner"> <nav role="navigation" class="navbar navbar-default"> <div c

  • Java 堆排序实例(大顶堆、小顶堆)

    Java 堆排序实例(大顶堆、小顶堆)

    堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法.堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点. 堆排序的平均时间复杂度为Ο(nlogn) . 算法步骤: 1. 创建一个堆H[0..n-1] 2. 把堆首(最大值)和堆尾互换 3. 把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置 4. 重复步骤2,直到堆的尺寸为1 堆: 堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:

  • 堆排序实例(Java数组实现)

    堆排序:利用大根堆 数组全部入堆,再出堆从后向前插入回数组中,数组就从小到大有序了. public class MaxHeap<T extends Comparable<? super T>> { private T[] data; private int size; private int capacity; public MaxHeap(int capacity) { this.data = (T[]) new Comparable[capacity + 1]; size =

  • Android7.0指纹服务FingerprintService实例介绍

    指纹服务是Android系统中一个较为简单的服务(相比于AMS,WMS等),也比较独立,功能上包括几点 指纹的录入与删除 指纹认证 指纹的安全策略(错误次数判定) 和其他的system service 一样,应用程序通过FingerprintManager实现与FingerprintService的通信,除了上面所说的功能之外,FingerprintManager提供了一些别的的接口,重要的接口都会要求系统级别的权限,并且也不是公开的api(指纹的录入,删除,重命名,重置错误计数等) /** *

  • c++实现超简单的贪吃蛇游戏实例介绍

    c++实现超简单的贪吃蛇游戏实例介绍

    目录 设计思路 实现代码 效果 设计思路         建议先将代码复制下来跑一遍再来看思路!!!         通俗易懂,请仔细看.         值得注意的是我给出的代码没有加墙体,如有需要自己添加.         也没有难度设计,同上. 地图大小(这里设计了墙体,代码中未实现) 设置一个整形数组map,其大小为1600,对应着地图的大小为1600,并初始化数组,令数组中的值全为0,0代表空地. 我们通过设定窗口的宽度为80,打印时每个map[i] 所对应的字符占两格位置即可实现每打

  • Android中Activity组件实例介绍

    Android中Activity组件实例介绍

    目录 Activity 概述 启动 Activity 的两种情况 关闭 Activity 总结 Activity 概述 在 Android 应用中,提供了 4 大基本组件,分别是 Activity.Service.BroadcastReceiver 和 ContentProvider.而 Activity 是 Android 应用最常见的组件之一.Activity 的中文意思是活动.在 Android 中,Activity 代表手机或者平板电脑中的一屏,它提供了和用户交互的可视化界面.在一个 A

  • 用python实现词云效果实例介绍

    用python实现词云效果实例介绍

    目录 什么是词云 一.特效预览 二.程序原理 三.程序源码 总结 什么是词云 词云其实就是就是对网络文本中出现频率较高的〝关键词〞予以视觉上的突出,形成〝关键词云层〞或〝关键词渲染〞从而过滤掉大量的文本信息 词云也是数据可视化的一种形式.给出一段文本,根据关键词的出现频率而生成的一幅图像,人们只要扫一眼就能够明白其文章主旨. 一.特效预览 词云图 二.程序原理 从给出的文本中,进行分词处理,然后将每个词出现的的频率进行统计从给出的背景图片上,读出图片信息将文本按照出现的频率进行画图,出现频率越高

  • python用pyecharts画地图实例介绍

    python用pyecharts画地图实例介绍

    版本pyecharts 分为 v0.5.X 和 v1 两个大版本,v0.5.X 和 v1 间不兼容,v1 是一个全新的版本 v0.5.X支持 Python2.7,3.4+v1仅支持 Python3.6+ 本文使用的是v1详见官方文档 数据来源只是学习方法,数据来源于网络查找 中国地图 from pyecharts.charts import Map import pyecharts.options as opts import os # 中国地图 province_distribution =

随机推荐