解读堆排序算法及用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)和(2),故它们均是堆,其对应的完全二叉树分别如最小堆示例和最大堆示例所示。
堆排序算法

2、最大堆和最小堆
(1)根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为最小堆。
(2)结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为最大堆。
注意:
(1)堆中任一子树亦是堆。
(2)以上讨论的堆实际上是二叉堆(Binary Heap),类似地可定义k叉堆。

3、堆排序的基本思路如下:
(1)把待排序数组构造成一个最大堆
(2)取出树的根(最大(小)值, 实际算法的实现并不是真正的取出)
(3)将树中剩下的元素再构造成一个最大堆(这里的构造和第1步不一样,具体看实现部分)
(4)重复2,3操作,直到取完所有的元素
(5)把元素按取出的顺序排列,即得到一个有序数组(在代码实现里是通过交换操作"无形中"完成的)
在开始实现算法先看几个结论(证明略):
(1)完全二叉树A[0:n-1]中的任意节点,其下标为 ii, 那么其子节点的下标分别是为2i+12i+1 和 2(i+1)2(i+1)
(2)大小为n的完全二叉树A[0:n-1],叶子节点中下标最小的是⌊n2⌋⌊n2⌋, 非叶子节点中下标最大的是⌊n2⌋−1⌊n2⌋−1
(3)如果数组是一个最大堆,那么最大元素就是A[0]
(4)最大堆中任意节点的左右子树也是最大堆
 
4、实现示例
这里的算法实现使用的是最大堆,首先来解决由数组建立最大堆的问题:

// 用于计算下标为i的节点的两个子节点的下标值
#define LEFT(i) (2 * (i) + 1)
#define RIGHT(i) (2 * ((i) + 1))

/* 此函数把一颗二叉树中以node为根的子树变成最大堆。
 * 注意: 使用的前提条件是 node节点的左右子树(如果存在的话)都是最大堆。
 * 这个函数是整个算法的关键。
 */
void max_heapify(int heap[], int heap_size, int node)
{
  // 这里先不考虑整数溢出的问题
  // 先把注意力放在主要的功能上
  // 如果数据规模够大,int类型必然会溢出
  int l_child = LEFT(node);
  int r_child = RIGHT(node);
  int max_value = node;

  if (l_child < heap_size && heap[l_child] > heap[max_value])
  {
    max_value = l_child;
  }
  if (r_child < heap_size && heap[r_child] > heap[max_value])
  {
    max_value = r_child;
  }
  if (max_value != node)
  {
    swap_val(heap + node, heap + max_value);

    // 之后还要保证被交换的子节点构成的子树仍然是最大堆
    // 如果不是这个节点会继续"下沉",直到合适的位置
    max_heapify(heap, heap_size, max_value);
  }
}

/* 将一个数组构造成最大堆
 * 自底向上的利用max_heapify函数处理
 */
void build_max_heap(int heap[], int heap_size)
{
  if (heap_size < 2)
  {
    return;
  }
  int first_leaf = heap_size >> 1;//第一个叶子节点的下标

  int i;
  // 从最后一个非叶子节点开始自底向上构建,
  // 叶子节点都看作最大堆,因此可以使用max_heapify函数
  for (i = first_leaf - 1; i >= 0; i--)
  {
    max_heapify(heap, heap_size, i);
  }
}

函数max_heapify将指定子树的根节点"下沉"到合适的位置, 最终子树变成最大堆, 该过程最坏时间复杂度为O(logn)O(log⁡n)。函数build_max_heap自底向上的调用max_heapify, 最终整个数组满足最大堆,迭代过程的复杂度为O(nlogn)O(nlog⁡n), 因此整个函数的最坏时间复杂度也是O(nlogn)O(nlog⁡n)。 而如果当前数组已经是最大堆了,例如数组原本是降序排列的, 那么max_heapify过程的时间复杂度就是O(1)O(1), 此时build_max_heap的时间复杂度是O(n)O(n),这是最好的情况。

接着实现堆排序过程:

/* heap sort 主函数
 */
void heap_sort(int heap[], int heap_size)
{
  if (heap == NULL || heap_size < 2)
  {
    return;
  }
  //构建最大堆
  build_max_heap(heap, heap_size);

  int i;
  for (i = heap_size - 1; i > 0; i--)
  {
    /* 把当前树的根节点交换到末尾
     * 相当于取出最大值,树的规模变小。
     * 交换后的树不是最大堆,但是根的两颗子树依然是最大堆
     * 满足调用max_heapify的条件。之所以这样交换,
     * 是因为用max_heapify处理时间复杂度较低,
     * 如果不交换而直接"取出"heap[0], 此处可能要使用
     * build_max_heap重新建立最大堆,时间复杂度较大
     */
    swap_val(heap, heap + i);

    heap_size--;
    //维护最大堆
    max_heapify(heap, heap_size, 0);
  }
}

最终的堆排序算法中,build_max_heap的复杂度是已知的, 迭代部分和build_max_heap的实现类似,而且不难看出, 交换后的根元素在下一次建堆过程中必然下沉到堆底,因此无论情况好坏, 该迭代过程时间复杂度都是O(nlogn)O(nlog⁡n), 所以整个算法的最好最坏和平均时间复杂度都是O(nlogn)O(nlog⁡n)。
堆排序算法的空间复杂度是O(1)O(1),从实现上很容易看出来。

时间: 2016-06-06

C++归并排序算法实例

归并排序 归并排序算法是采用分治法的一个非常典型的应用.归并排序的思想是将一个数组中的数都分成单个的:对于单独的一个数,它肯定是有序的,然后,我们将这些有序的单个数在合并起来,组成一个有序的数列.这就是归并排序的思想.它的时间复杂度为O(N*logN). 代码实现 复制代码 代码如下: #include <iostream> using namespace std;   //将有二个有序数列a[first...mid]和a[mid...last]合并. void mergearray(int

C++冒泡排序算法实例

冒泡排序 大学学习数据结构与算法最开始的时候,就讲了冒泡排序:可见这个排序算法是多么的经典.冒泡排序是一种非常简单的排序算法,它重复地走访过要排序的数列,每一次比较两个数,按照升序或降序的规则,对比较的两个数进行交换.比如现在我要对以下数据进行排序: 10 3 8 0 6 9 2 当使用冒泡排序进行升序排序时,排序的步骤是这样的: 3 10 8 0 6 9 2  // 10和3进行对比,10>3,交换位置 3 8 10 0 6 9 2  // 10再和8进行对比,10>8,交换位置 3 8 0

C++中十种内部排序算法的比较分析

C++中十种内部排序算法的比较分析 #include<iostream> #include<ctime> #include<fstream> using namespace std; #define MAXSIZE 1000 //可排序表的最大长度 #define SORTNUM 10 //测试10中排序方法 #define max 100 //基数排序时数据的最大位数不超过百位: typedef struct node { int data3; int next; }

C++实现各种排序算法类汇总

C++可实现各种排序算法类,比如直接插入排序.折半插入排序.Shell排序.归并排序.简单选择排序.基数排序.对data数组中的元素进行希尔排序.冒泡排序.递归实现.堆排序.用数组实现的基数排序等. 具体代码如下: #ifndef SORT_H #define SORT_H #include <iostream> #include <queue> using namespace std; // 1.直接插入排序 template<class ElemType> void

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

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

C++选择排序算法实例

选择排序 选择排序是一种简单直观的排序算法,它的工作原理如下.首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 选择排序的主要优点与数据移动有关.如果某个元素位于正确的最终位置上,则它不会被移动.选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换.在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常

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

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

C++插入排序算法实例

插入排序 没事喜欢看看数据结构和算法,增加自己对数据结构和算法的认识,同时也增加自己的编程基本功.插入排序是排序中比较常见的一种,理解起来非常简单.现在比如有以下数据需要进行排序: 10 3 8 0 6 9 2 当使用插入排序进行升序排序时,排序的步骤是这样的: 10 3 8 0 6 9 2 // 取元素3,去和10进行对比 3 10 8 0 6 9 2 // 由于10比3大,将10向后移动,将3放置在原来10的位置:再取8与前一个元素10进行对比 3 8 10 0 6 9 2 // 同理移动1

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

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

php仿微信红包分配算法的实现方法

本文实例讲述了php仿微信红包分配算法的实现方法.分享给大家供大家参考,具体如下: /** * 红包分配:把一定金额随机分配给指定人数 * * @param int $money 用于分配的金额 * @param int $num 分配人数 */ function RandomMoney($money, $num) { echo "$money元随机分成$num份分别是:<br/>"; $remain=$money; $use=0; for ($i=1; $i<$nu

PHP二分查找算法的实现方法示例

本文实例讲述了PHP二分查找算法的实现方法.分享给大家供大家参考,具体如下: 二分查找法需要数组是一个有序的数组 假设我们的数组是一个递增的数组,首先我们需要找到数组的中间位置. 1. 要知道中间位置就需要知道起始位置和结束位置,然后取出中间位置的值来和我们的值做对比. 2. 如果中间值大于我们的给定值,说明我们的值在中间位置之前,此时需要再次二分,因为在中间之前,所以我们需要变的值是结束位置的值,此时结束位置的值应该是我们此时的中间位置. 3. 反之,如果中间值小于我们给定的值,那么说明给定值

c#哈希算法的实现方法及思路

有想过hash["A1"] = DateTime.Now;这句是怎么实现的吗?我们来重温下学校时代就学过的哈希算法吧. 我们要写个class,实现如下主程序调用: 复制代码 代码如下: static void Main(string[] args)        {            MyHash hash = new MyHash();            hash["A1"] = DateTime.Now;            hash["A2

php菜单/评论数据递归分级算法的实现方法

在开发过程中经常会遇到分级场景,如菜单分级.评论.商品类型分级等:在同一张mysql数据表中可能设计单表结构,如同如下数据: $menuList = [ [ 'id' => 1,'parent_id' => 0, 'name' => '节点1'], [ 'id' => 2,'parent_id' => 1, 'name' => '节点1-1'], [ 'id' => 3,'parent_id' => 0, 'name' => '节点2'], [ 'id

java几种排序算法的实现及简单分析

本文实例讲述了java几种排序算法的实现及简单分析.分享给大家供大家参考.具体如下: package test; public class first { /*普通的插入排序*/ public void insertSort(int[] list) { int i, j; list[0] = -999; //相当于设置一个监视哨兵,不用判断是否越界, //但要求数组从第二个数开始即i=1开始存储 for (i = 1; i < list.length; i++) { j = i; while (

Linux内核中红黑树算法的实现详解

一.简介 平衡二叉树(BalancedBinary Tree或Height-Balanced Tree) 又称AVL树.它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1.若将二叉树上结点的平衡因子BF(BalanceFactor)定义为该结点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只可能是-1.0和1.(此段定义来自严蔚敏的<数据结构(C语言版)>) 红黑树 R-B Tree,全称是Red-B

应用OpenCV和Python进行SIFT算法的实现详解

应用OpenCV和Python进行SIFT算法的实现 如下图为进行测试的gakki101和gakki102,分别验证基于BFmatcher.FlannBasedMatcher等的SIFT算法,对比其优劣.为体现出匹配效果对于旋转特性的优势,将图gakki101做成具有旋转特性的效果. 基于BFmatcher的SIFT实现 BFmatcher(Brute-Force Matching)暴力匹配,应用BFMatcher.knnMatch( )函数来进行核心的匹配,knnMatch(k-nearest

python常用排序算法的实现代码

这篇文章主要介绍了python常用排序算法的实现代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 排序是计算机语言需要实现的基本算法之一,有序的数据结构会带来效率上的极大提升. 1.插入排序 插入排序默认当前被插入的序列是有序的,新元素插入到应该插入的位置,使得新序列仍然有序. def insertion_sort(old_list): n=len(old_list) k=0 for i in range(1,n): temp=old_lis

php 二维数组快速排序算法的实现代码

php 二维数组快速排序算法的实现代码 二维数组排序算法与一维数组排序算法基本理论都是一样,都是通过比较把小的值放在左变的数组里,大的值放在右边的数组里在分别递归. 实例代码: <?php class Bubble { private function __construct() { } private static function sortt($data) { if (count ( $data ) <= 1) { return $data; } $tem = $data [0]['sco