堆:(二叉)堆数据结构是一种数组对象。它可以被视为一棵完全二叉树,树中每个结点与数组中存放该结点值的那个元素对应。 二叉堆有两种:最大堆和最小堆(小根堆)。 最大堆:所有节点的子节点比其自身小的堆。 堆排序:堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单 在堆排序算法中,使用的是最大堆,最小堆通常在构造优先级队列时使用。 再次提醒大家,去看看《算法导论》里的第六章-堆排序。因为书上讲的太详细了,所以我也就不再多说。 这里我把《算法导论》上的伪代码用C/C++实现了,每个函数我都用自己的理解写出来了,如果大家还不懂,可以留言。
最小堆:所有节点的子节点比其自身大的堆。
#include <iostream> using namespace std; // 输出当前堆的排序状况 void PrintArray(int data[], int size) { for (int i=1; i<=size; ++i) cout <<data[i]<<" "; cout<<endl; } // 堆化,保持堆的性质 // MaxHeapify让a[i]在最大堆中"下降", // 使以i为根的子树成为最大堆 void MaxHeapify(int *a, int i, int size) { int lt = 2*i, rt = 2*i+1; int largest; if(lt <= size && a[lt] > a[i]) largest = lt; else largest = i; if(rt <= size && a[rt] > a[largest]) largest = rt; if(largest != i) { int temp = a[i]; a[i] = a[largest]; a[largest] = temp; MaxHeapify(a, largest, size); } } // 建堆 // 自底而上地调用MaxHeapify来将一个数组a[1..size]变成一个最大堆 // void BuildMaxHeap(int *a, int size) { for(int i=size/2; i>=1; --i) MaxHeapify(a, i, size); } // 堆排序 // 初始调用BuildMaxHeap将a[1..size]变成最大堆 // 因为数组最大元素在a[1],则可以通过将a[1]与a[size]互换达到正确位置 // 现在新的根元素破坏了最大堆的性质,所以调用MaxHeapify调整, // 使a[1..size-1]成为最大堆,a[1]又是a[1..size-1]中的最大元素, // 将a[1]与a[size-1]互换达到正确位置。 // 反复调用Heapify,使整个数组成从小到大排序。 // 注意: 交换只是破坏了以a[1]为根的二叉树最大堆性质,它的左右子二叉树还是具备最大堆性质。 // 这也是为何在BuildMaxHeap时需要遍历size/2到1的结点才能构成最大堆,而这里只需要堆化a[1]即可。 void HeapSort(int *a, int size) { BuildMaxHeap(a, size); PrintArray(a, size); int len = size; for(int i=size; i>=2; --i) { int temp = a[1]; a[1] = a[i]; a[i] = temp; len--; MaxHeapify(a, 1, len); cout << "中间过程:"; PrintArray(a, size); } } int main() { int size; int arr[100]; cout << "Input the num of elements:\n"; cin >> size; cout << "Input the elements:\n"; for(int i=1; i<=size; ++i) cin >> arr[i]; cout << endl; HeapSort(arr, size); cout << "最后结果:"; PrintArray(arr, size); }
发表评论
-
析构函数为虚函数的原因
2012-09-09 11:42 830我们知道,用C++开发的时候,用来做基类的类的析构函数 ... -
hash的应用
2012-08-31 23:02 959第一部分为一道百度面试题Top K算法的详解;第二部分为关 ... -
微软智力题
2012-08-29 19:59 564第一组1.烧一根不均匀的绳,从头烧到尾总共需要1个小时。现在有 ... -
C++不能被继承的类
2012-08-27 20:16 1054一个类不能被继承, ... -
括号对齐问题
2012-08-27 10:47 1406解法一:左右括号成一对则抵消 可以 ... -
树的遍历
2012-08-19 10:43 717/****************************** ... -
多态赋值
2012-08-14 16:16 828#include <iostream> usi ... -
static变量与static函数(转)
2012-08-13 10:15 743一、 static 变量 static变量大致分为三种用法 ... -
不用sizeof判断16位32位
2012-08-10 15:21 1699用C++写个程序,如何判断一个操作系统是16位还是3 ... -
找出连续最长的数字串(百度面试)
2012-08-09 15:15 1144int maxContinuNum(const char*in ... -
顺序栈和链栈
2012-08-06 10:01 795顺序栈:话不多说直接上代码 #include ... -
队列的数组实现和链表实现
2012-08-05 16:20 1023话不多少,数组实现上代码: #include<i ... -
KMP算法详解
2012-08-02 21:40 879KMP算法: 是在一个“主文本字符串” ... -
字符串的最长连续重复子串
2012-08-01 15:05 9768两种方法: 循环两次寻找最长的子串: <方法一> ... -
寻找一个字符串连续出现最多的子串的方法(转)
2012-07-31 21:19 974算法描述首先获得后缀数组,然后1.第一行第一个字符a,与第二行 ... -
字符串的循环移位
2012-07-31 16:52 974假设字符串:abcdefg 左循环两位:cdefgab 右 ... -
一次谷歌面试趣事(转)
2012-07-31 15:26 762很多年前我进入硅谷 ... -
约瑟夫环问题(循环链表)
2012-07-30 21:31 1285题目描述:n只猴子要选大王,选举方法如下:所有猴子按 1, ... -
面试之单链表
2012-07-30 20:18 7241、编程实现一个单链表的建立/测长/打印。 ... -
多重继承内存地址问题
2012-07-30 15:55 725[cpp] view plaincopy ...
相关推荐
堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在本场景中,我们关注的是堆排序的源代码,它适用于openSUSE 11.4操作系统,并且是使用GCC version 4.5.1编译器编译的。在这个名为"sort...
本主题将深入探讨四种常见的排序算法:堆排序、快速排序以及两种未在标题中明确提到但同样重要的排序方法——基数排序和计数排序。 首先,让我们详细了解一下堆排序。堆排序是一种基于比较的排序算法,利用了数据...
堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在大顶堆中,父节点的值总是大于或等于其子节点;而在小顶堆中,父节点的值总是小于或等于其子节点。在C++中,我们可以利用STL中的`...
【堆排序算法详解】 堆排序是一种高效的比较排序算法,其主要思想是利用堆这种数据结构进行数据的排序。堆是一个近似完全二叉树的结构,同时满足堆的性质:即父节点的键值总是大于或等于(在最大堆中)或小于或等于...
堆排序是一种基于比较的排序算法,它利用了数据结构中的“堆”这一概念。在计算机科学中,堆通常被理解为一个完全二叉树,其中每个父节点的值都大于或等于(大顶堆)或小于或等于(小顶堆)其子节点的值。堆排序算法...
在这个名为“学生成绩管理中实现堆排序”的项目中,我们看到一个C++编写的学生成绩管理系统,它使用了堆排序方法来管理并排序学生的成绩。 首先,让我们详细了解一下堆。堆通常是一个完全二叉树,可以分为最大堆和...
本文将深入探讨四种在C++中实现的常见排序算法:插入排序、冒泡排序、堆排序和快速排序。这些算法各有特点,适用于不同的场景,理解并掌握它们对于提升编程能力至关重要。 1. **插入排序**: 插入排序是一种简单的...
### 数据结构课程设计实验报告——堆排序 #### 一、堆排序概述 堆排序是一种基于树形选择的排序算法,其核心在于利用完全二叉树的性质进行元素的选择与排序。在排序过程中,将待排序的数据集合视为一颗完全二叉树...
数据结构排序 堆排序 堆排序是一种常用的排序算法,它使用大堆进行排序。下面是堆排序的详细知识点说明: 堆排序定义 堆排序是一种比较排序算法,它使用大堆(max heap)来对数组进行排序。堆排序的时间复杂度为O...
1、 实现堆排序算法。 2、 理论分析并实验验证堆排序算法的时间复杂度。
堆排序是一种基于比较的排序算法,它通过构造一个近似完全二叉树的堆结构来实现数据的排序。在此,我们将深入探讨堆排序的基本概念、原理以及如何通过编程实现。 一、堆排序的概念 堆是一个近似完全二叉树的结构,...
在ACM(国际大学生程序设计竞赛)中,堆排序是一种常用且高效的排序算法,对于解决时间限制严格的在线问题尤其有用。本篇文章将深入探讨堆排序的原理、实现以及如何将其应用到ACM竞赛中。 首先,堆是一个近似完全...
堆排序是一种基于比较的排序算法,它通过构建和调整二叉堆来实现数据的排序。在二叉堆中,每个父节点的值都大于或等于其子节点的值,这样的堆被称为最大堆。堆排序的基本步骤包括建堆、交换根节点与最后一个元素、...
堆排序是一种基于比较的排序算法,它的效率高且实现简单。在本文中,我们将深入探讨堆排序的原理,以及如何在实际编程中实现它。 首先,我们要理解什么是堆。堆是一种特殊的树形数据结构,每个节点都有一个值,并且...
堆排序是一种基于比较的排序算法,它利用了完全二叉树的数据结构特性,通过堆的性质进行元素的排序。在堆排序中,堆被定义为满足以下性质的完全二叉树:对于每个非叶子节点,其值大于或等于(在大根堆中)或小于或...
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
全面的排序算法实现,包括插入排序、合并排序、堆排序、快速排序。 堆排序:HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序:InSertion_Sort 讲解详见...
堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在计算机科学中,堆通常被理解为一种特殊的完全二叉树,其中每个父节点的值都大于或等于(对于大顶堆)或小于或等于(对于小顶堆)其子...
直接插入排序、冒泡排序、快速排序、直接选择排序、堆排序和二路归并排序是计算机科学中经典的排序算法,它们在数据处理和算法学习中占有重要地位。这些排序算法各有特点,适用场景不同,下面将逐一详细介绍,并结合...
堆排序是一种基于比较的排序算法,它通过构造一个近似完全二叉树的堆数据结构来实现排序。在计算机科学中,堆是一个可以被看作是一棵树形结构的数据集合,其中每个父节点的值都大于或等于其子节点的值(大顶堆)或...