PHP排序算法之堆排序(Heap Sort)实例详解

1. 不得不说说二叉树 vnsc威尼斯城官方网站,要询问堆首先得询问一下二叉树,在管理器科学中,二叉树是种种节点最多有多少个子树的树结构。常常子树被称作“左子树”(left
subtree)和“右子树”(right
subtree)。二叉树常被用于落到实处二叉查找树和二叉堆。
二叉树的种种结点至两独有二棵子树(官样文章度大于 2
的结点),二叉树的子树有左右之分,次序不可能颠倒。二叉树的第 i 层至多有 2i

图像和文字详解Heap Sort堆排序算法及JavaScript的代码完毕,heap堆排序

1. 不得不说说二叉树 要打听堆首先得询问一下二叉树,在微型计算机科学中,二叉树是各类节点最多有三个子树的树结构。平日子树被称作“左子树”(left
subtree)和“右子树”(right
subtree)。二叉树常被用来落到实处二叉查找树和二叉堆。
二叉树的各种结点至两独有二棵子树(官样文章度大于 2
的结点),二叉树的子树有左右之分,次序不可能颠倒。二叉树的第 i 层至多有 2i

  • 1 个结点;深度为 k 的二叉树至多有 2k – 1 个结点;对其它一棵二叉树
    T,如若其终端结点数为 n0,度为 2 的结点数为 n2,则n0 = n2 + 1。
    树和二叉树的三个重大出入:
    树的结点个数至少为 1,而二叉树的结点个数可以为 0
    树中结点的最大度数未有限定,而二叉树结点的最大度数为 2
    树的结点无左、右之分,而二叉树的结点有左、右之分
    二叉树又分为完全二叉树(complete binary tree)和满二叉树(full binary
    tree)
    满二叉树:一棵深度为 k,且有 2k – 1 个节点称之为满二叉树

vnsc威尼斯城官方网站 1

(深度为 3 的满二叉树 full binary tree)
全然二叉树:深度为 k,有 n
个节点的二叉树,当且仅当其每二个节点都与深度为 k 的满二叉树中序号为 1 至
n 的节点对应时,称之为完全二叉树

vnsc威尼斯城官方网站 2

(深度为 3 的通通二叉树 complete binary tree)
2. 怎么样是堆? 堆(二叉堆)能够算得一棵完全的二叉树,完全二叉树的五个“卓越”的本性是,除了最尾巴部分之外,每一层都以满的,这使得堆能够选拔数组来表示(普通的相似的二叉树日常用链表作为主旨容器表示),每一个结点对应数组中的一个成分。
正如图,是八个堆和数组的相互关系

vnsc威尼斯城官方网站 3

(堆和数组的相互关系)
对此给定的某部结点的下标
i,能够很轻巧的总计出那一个结点的父结点、孩子结点的下标:
Parent(i) = floor(i/2),i 的父节点下标
Left(i) = 2i,i 的左子节点下标
Right(i) = 2i + 1,i 的右子节点下标

vnsc威尼斯城官方网站 4

二叉堆一般分为三种:最大堆和微小堆。
最大堆:
最大堆中的最大成分值出现在根结点(堆顶)
堆中每一种父节点的因素值都大于等于其子女结点(假设存在)

vnsc威尼斯城官方网站 5

(最大堆)
最小堆:
细微堆中的最小成分值出现在根结点(堆顶)
堆中各类父节点的成分值都低于等于其儿女结点(假使存在)

vnsc威尼斯城官方网站 6

(最小堆)
3. 堆排序原理 堆排序正是把最大堆堆顶的最大数收取,将剩下的堆继续调度为最大堆,再一次将堆顶的最大数抽取,那么些进度持续到剩余数独有贰个时截至。在堆中定义以下三种操作:
最大堆调节(马克斯-Heapify):将堆的后边子节点作调节,使得子节点长久远小于父节点
开创最大堆(Build-马克斯-Heap):将堆全数数据再度排序,使其成为最大堆
堆排序(Heap-Sort):移除位在第叁个数据的根节点,并做最大堆调节的递归运算
此伏彼起实行下边包车型客车切磋前,要求留心的一个难点是:数组都是Zero-Based,那就代表大家的堆数据结构模型要发生转移

vnsc威尼斯城官方网站 7

(Zero-Based)
对应的,几个总括公式也要作出相应调解:
Parent(i) = floor((i-1)/2),i 的父节点下标
Left(i) = 2i + 1,i 的左子节点下标
Right(i) = 2(i + 1),i 的右子节点下标
最大堆调解(MAX‐HEAPIFY)的意义是维持最大堆的习性,是开创最大堆的大旨子程序,作用进程如图所示:

vnsc威尼斯城官方网站 8

(Max-Heapify)
是因为一遍调节后,堆还是违反堆性质,所以需求递归的测量检验,使得全部堆都满意堆性质,用
JavaScript 能够代表如下:

/**
 * 从 index 开始检查并保持最大堆性质
 *
 * @array
 *
 * @index 检查的起始下标
 *
 * @heapSize 堆大小
 *
 **/
function maxHeapify(array, index, heapSize) {
 var iMax = index,
   iLeft = 2 * index + 1,
   iRight = 2 * (index + 1);

 if (iLeft < heapSize && array[index] < array[iLeft]) {
  iMax = iLeft;
 }

 if (iRight < heapSize && array[iMax] < array[iRight]) {
  iMax = iRight;
 }

 if (iMax != index) {
  swap(array, iMax, index);
  maxHeapify(array, iMax, heapSize); // 递归调整
 }
}

function swap(array, i, j) {
 var temp = array[i];
 array[i] = array[j];
 array[j] = temp;
}

一般说来来讲,递归首要用在分治法中,而那边并无需分治。何况递归调用必要压栈/清栈,和迭代比较,品质上有略微的劣点。当然,依照20/80原理,那是能够忽略的。然则倘诺您感觉用递归会让投机心灵过不去的话,也得以用迭代,例如上边那样:

/**
 * 从 index 开始检查并保持最大堆性质
 *
 * @array
 *
 * @index 检查的起始下标
 *
 * @heapSize 堆大小
 *
 **/
function maxHeapify(array, index, heapSize) {
 var iMax, iLeft, iRight;
 while (true) {
  iMax = index;
  iLeft = 2 * index + 1;
  iRight = 2 * (index + 1);
  if (iLeft < heapSize && array[index] < array[iLeft]) {
   iMax = iLeft;
  }

  if (iRight < heapSize && array[iMax] < array[iRight]) {
   iMax = iRight;
  }

  if (iMax != index) {
   swap(array, iMax, index);
   index = iMax;
  } else {
   break;
  }
 }
}

function swap(array, i, j) {
 var temp = array[i];
 array[i] = array[j];
 array[j] = temp;
}

制造最大堆(Build-马克斯-Heap)的效果是将三个数组改换成二个最大堆,接受数组和堆大小多个参数,Build-马克斯-Heap
将自下而上的调用 马克斯-Heapify 来改动数组,创立最大堆。因为 Max-Heapify
可以有限协理下标 i 的结点之后结点都满意最大堆的特性,所以自下而上的调用
Max-Heapify 能够在改动进程中保持这一质量。若是最大堆的多寡成分是 n,那么
Build-马克斯-Heap 从 Parent(n) 发轫,往上家家户户调用 马克斯-Heapify。流程如下:

vnsc威尼斯城官方网站 9

用 JavaScript 描述如下:

function buildMaxHeap(array, heapSize) {
 var i,
   iParent = Math.floor((heapSize - 1) / 2);

 for (i = iParent; i >= 0; i--) {
  maxHeapify(array, i, heapSize);
 }
}

堆排序(Heap-Sort)是堆排序的接口算法,Heap-Sort先调用Build-马克斯-Heap将数组改变为最大堆,然后将堆顶和堆底成分调换,之后将尾巴部分上涨,最后重复调用马克斯-Heapify保持最大堆性质。由于堆顶成分必然是堆中最大的因素,所以一回操作之后,堆中留存的最大体素被分手出堆,重复n-1次未来,数组排列实现。整个工艺流程如下:

vnsc威尼斯城官方网站 10

用 JavaScript 描述如下:

function heapSort(array, heapSize) {

 buildMaxHeap(array, heapSize);

 for (int i = heapSize - 1; i > 0; i--) {
  swap(array, 0, i);
  maxHeapify(array, 0, i);
 } 
}

4.JavaScript 语言落成 末段,把上面的整治为完全的 javascript 代码如下:

function heapSort(array) {

 function swap(array, i, j) {
  var temp = array[i];
  array[i] = array[j];
  array[j] = temp;
 }

 function maxHeapify(array, index, heapSize) {
  var iMax,
   iLeft,
   iRight;
  while (true) {
   iMax = index;
   iLeft = 2 * index + 1;
   iRight = 2 * (index + 1);

   if (iLeft < heapSize && array[index] < array[iLeft]) {
    iMax = iLeft;
   }

   if (iRight < heapSize && array[iMax] < array[iRight]) {
    iMax = iRight;
   }

   if (iMax != index) {
    swap(array, iMax, index);
    index = iMax;
   } else {
    break;
   }
  }
 }

 function buildMaxHeap(array) {
  var i,
   iParent = Math.floor(array.length / 2) - 1;

  for (i = iParent; i >= 0; i--) {
   maxHeapify(array, i, array.length);
  }
 }

 function sort(array) {
  buildMaxHeap(array);

  for (var i = array.length - 1; i > 0; i--) {
   swap(array, 0, i);
   maxHeapify(array, 0, i);
  }
  return array;
 }

 return sort(array);
}

5.堆排序算法的接纳

(1)算法质量/复杂度 堆排序的年华复杂度特别平静(大家得以见到,对输入数据不敏感),为O(n㏒n)复杂度,最棒状态与最坏情状亦然。
不过,其空间复杂度依达成分化而差别。上面即探究了三种常见的复杂度:O(n)与O(1)。本着节约空间的规范,小编推荐O(1)复杂度的章程。

(2)算法稳固性 堆排序存在大气的筛选和移动进程,属于不平静的排序算法。

(3)算法适用场景 堆排序在创制堆和调度堆的进程中会发生异常的大的付出,在要素少的时候并不适用。可是,在要素比较多的景色下,依然不错的四个增选。特别是在缓和诸如“前n大的数”一类主题材料时,大约是首荐算法。

Sort堆排序算法及JavaScript的代码完毕,heap堆排序 1. 只可以说说二叉树
要打听堆首先得询问一下二叉树,在管理器科学中,二叉…

算法引入:

PHP实现排序堆排序(Heap Sort)算法,堆排序heap

算法引入:

在这里本俗世接援用《大话数据结构》里面包车型大巴开始:

在后边讲到 轻便选用排序 ,它在待排序的 n
个记录中甄选三个比十分的小的笔录要求相比 n – 1
次,本来那也能够清楚,查找第1个数据需求相比较这么数次是平常的,不然怎么掌握他是小小的的笔录。

缺憾的是,那样的操作并不曾把每一遍的比较结实保存下去,在后一趟的可比重,有多数相比较在前一趟已经做过了,但由于前一趟排序时未保存那些比较结实,所现在一趟排序时又重新实行了那么些相比较操作,由此记录的可比次数非常多。

一经得以成功每便在增选到微小记录的同期,并依赖相比较结实对其余记录做出相应的调动,那样排序的一体化效用就能极高了。而堆排序,正是对简易选用排序实行的一种立异,这种改进的功能是拾叁分显眼的。

基本思维:

在介绍堆排序在此之前,大家先来介绍一下堆:

《大话数据结构》里的定义:堆
是颇具下列性质的一心二叉树:每种节点的值都大于或等于其左右男女节点的值,成为大顶堆(大根堆);只怕各种节点的值都自愧不及或等于其左右节点的值,成为小顶堆(小根堆)。

马上自家在收看此间的时候也对有“堆是否是完全二叉树”有过疑问,互连网也会有说不是一心二叉树的,可是无论是堆是还是不是一心二叉树,尚且保留神见。大家假诺知道,在那边大家采纳完全二叉树方式的大根堆(小跟堆),首就算为着便于存款和储蓄和计算(前边大家会看出带来的实惠)。

vnsc威尼斯城官方网站 11

堆排序算法:

堆排序正是行使堆(假若利用大根堆)实行排序的点子,它的主导观念是:将待排序的队列构产生二个大根堆。此时,整个种类的最大值就是堆顶的根节点。将它移走(其实便是将其与堆数组的终极元素沟通,此时末尾成分正是最大值),然后将盈余的
n – 1 个系列重新布局成贰个堆,这样就能够获得 n
个因素中的次小的值。如此一再施行,便能得到二个照猫画虎体系了。

大根堆排序算法的基本操作:

①建堆,建堆是反复调治堆的经过,从 len/2
处开头调治,平素到第一个节点,此处 len
是堆瓜时素的个数。建堆的进程是线性的进程,从 len/2 到 0
处一向调用调节堆的经过,也就是 o(h1) + o(h2) …+ o(hlen/2) 在这之中 h
表示节点的纵深, len/2 表示节点的个数,那是一个求和的进程,结果是线性的
O(n)。

②调度堆:调解堆在构建堆的经过中会用到,並且在堆排序进程中也会用到。利用的观念是相比节点i和它的孩子节点
left(i) ,
right(i),选出三者最大(只怕最小)者,要是最大(小)值不是节点i而是它的一个儿女节点,那边互相节点i和该节点,然后再调用调治堆进程,那是一个递归的历程。调节堆的历程时间复杂度与堆的纵深有提到,是
lgn 的操作,因为是顺着深度方向实行调解的。

③堆排序:堆排序是选用方面的八个进程来实行的。首先是依据成分创设堆。然后将堆的根节点取出(一般是与最后二个节点进行置换),将前段时间len-1
个节点继续开展堆调解的长河,然后再将根节点抽取,那样一向到全数节点都收取。堆排序进度的时辰复杂度是
O(nlgn)。因为建堆的小时复杂度是 O(n)(调用贰回);调节堆的时刻复杂度是
lgn,调用了 n-1 次,所以堆排序的时日复杂度是 O(nlgn)。

在这些进度中是内需大量的图示技巧看的驾驭的,可是作者懒。。。。。。

算法完结:

<?php

//堆排序(对简单选择排序的改进)

function swap(array &$arr,$a,$b){
 $temp = $arr[$a];
 $arr[$a] = $arr[$b];
 $arr[$b] = $temp;
}

//调整 $arr[$start]的关键字,使$arr[$start]、$arr[$start+1]、、、$arr[$end]成为一个大根堆(根节点最大的完全二叉树)
//注意这里节点 s 的左右孩子是 2*s + 1 和 2*s+2 (数组开始下标为 0 时)
function HeapAdjust(array &$arr,$start,$end){
 $temp = $arr[$start];
 //沿关键字较大的孩子节点向下筛选
 //左右孩子计算(我这里数组开始下标识 0)
 //左孩子2 * $start + 1,右孩子2 * $start + 2
 for($j = 2 * $start + 1;$j <= $end;$j = 2 * $j + 1){
  if($j != $end && $arr[$j] < $arr[$j + 1]){
   $j ++; //转化为右孩子
  }
  if($temp >= $arr[$j]){
   break; //已经满足大根堆
  }
  //将根节点设置为子节点的较大值
  $arr[$start] = $arr[$j];
  //继续往下
  $start = $j;
 }
 $arr[$start] = $temp;
}

function HeapSort(array &$arr){
 $count = count($arr);
 //先将数组构造成大根堆(由于是完全二叉树,所以这里用floor($count/2)-1,下标小于或等于这数的节点都是有孩子的节点)
 for($i = floor($count / 2) - 1;$i >= 0;$i --){
  HeapAdjust($arr,$i,$count);
 }
 for($i = $count - 1;$i >= 0;$i --){
  //将堆顶元素与最后一个元素交换,获取到最大元素(交换后的最后一个元素),将最大元素放到数组末尾
  swap($arr,0,$i); 
  //经过交换,将最后一个元素(最大元素)脱离大根堆,并将未经排序的新树($arr[0...$i-1])重新调整为大根堆
  HeapAdjust($arr,0,$i - 1);
 }
}

$arr = array(9,1,5,8,3,7,4,6,2);
HeapSort($arr);
var_dump($arr);

光阴复杂度深入分析:

它的运维时刻假设是消耗在伊始塑造对和在重新创设堆屎的往往筛选上。

总体上的话,堆排序的时辰复杂度是
O(nlogn)。由于堆排序对原始记录的排序状态并不灵动,由此它不管最棒、最差和平均时间复杂度都是O(nlogn)。那在质量上显明要远远好于冒泡、轻易选取、直接插入的 O(n^2)
的光阴复杂度了。

堆排序是一种不安定排序方法。

本篇博客参考自《大话数据结构》,在此仅作记录,方便未来翻看,大神勿喷!

Sort)算法,堆排序heap
算法引进: 在这里小编平昔援引《大话数据结构》里面包车型地铁上马: 在前方讲到
轻便选用排序 ,…

本文实例叙述了PHP排序算法之堆排序(Heap
Sort)。共享给大家供大家参照他事他说加以考察,具体如下:

  • 1 个结点;深度为 k 的二叉树至多有 2k – 1 个结点;对别的一棵二叉树
    T,借使其终端结点数为 n0,度为 2 的结点数为 n2,则n0 = n2 + 1。
    树和二叉树的四个第一出入:
    树的结点个数至少为 1,而二叉树的结点个数可以为 0
    树中结点的最大度数未有范围,而二叉树结点的最大度数为 2
    树的结点无左、右之分,而二叉树的结点有左、右之分
    二叉树又分为完全二叉树(complete binary tree)和满二叉树(full binary
    tree)
    满二叉树:一棵深度为 k,且有 2k – 1 个节点称之为满二叉树

在此地本身直接引用《大话数据结构》里面包车型客车最早:

算法引入:

vnsc威尼斯城官方网站 12

在前边讲到 简单的讲选用排序
,它在待排序的 n 个记录中甄选三个非常的小的笔录必要比较 n – 1
次,本来那也能够知道,查找第三个数据须要相比较这么数十次是寻常的,不然怎么掌握她是一点都不大的笔录。

在此处本身直接援用《高调数据结构》里面包车型地铁起来:

(深度为 3 的满二叉树 full binary tree)
统统二叉树:深度为 k,有 n
个节点的二叉树,当且仅当其每一个节点都与深度为 k 的满二叉树中序号为 1 至
n 的节点对应时,称之为完全二叉树

缺憾的是,那样的操作并不曾把每趟的可比结实保存下去,在后一趟的相当的重,有成都百货上千相比较在前一趟已经做过了,但由于前一趟排序时未保存这么些相比较结实,所未来一趟排序时又重新奉行了这么些相比操作,由此记录的相比次数相当多。

在前面讲到 简言之选择排序
,它在待排序的 n 个记录中选拔三个细小的笔录须求比较 n – 1
次,本来那也能够知道,查找第三个数据必要相比较这么多次是正规的,否则怎么样晓得她是非常小的记录。

vnsc威尼斯城官方网站 13

若是能够变成每趟在增选到微小记录的还要,并依照相比较结实对其余记录做出相应的调动,那样排序的一体化作用就能充裕高了。而堆排序,正是对简易选取排序进行的一种革新,这种革新的功力是可怜令人瞩指标。

惋惜的是,那样的操作并从未把每一遍的可比结实保存下来,在后一趟的相当重,有十分的多相比在前一趟已经做过了,但出于前一趟排序时未保存这几个比较结实,所未来一趟排序时又再一次试行了这么些相比较操作,因此记录的可比次数非常多。

(深度为 3 的完全二叉树 complete binary tree)
2. 什么样是堆? 堆(二叉堆)能够说是一棵完全的二叉树,完全二叉树的一个“优异”的性能是,除了最头部之外,每一层都是满的,这使得堆能够利用数组来表示(普通的一般的二叉树常常用链表作为宗旨容器表示),每三个结点对应数组中的四个因素。
一般来讲图,是三个堆和数组的互相关系

主导思维:

一经能够做到每趟在增选到细微记录的还要,并依据相比较结实对其余记录做出相应的调解,这样排序的完全效用就可以特别高了。而堆排序,正是对简易选取排序举行的一种革新,这种立异的职能是拾贰分醒目标。

vnsc威尼斯城官方网站 14

在介绍堆排序在此之前,大家先来介绍一下堆:

焦点情想:

(堆和数组的彼此关系)
对此给定的某部结点的下标
i,能够很轻巧的预计出那一个结点的父结点、孩子结点的下标:
Parent(i) = floor(i/2),i 的父节点下标
Left(i) = 2i,i 的左子节点下标
Right(i) = 2i + 1,i 的右子节点下标

《大话数据结构》里的概念:堆
是装有下列性质的通通二叉树:每一种节点的值都大于或等于其左右儿女节点的值,成为大顶堆(大根堆);大概种种节点的值都低于或等于其左右节点的值,成为小顶堆(小根堆)。

在介绍堆排序此前,大家先来介绍一下堆:

vnsc威尼斯城官方网站 15

当下本身在探问此间的时候也对有“堆是或不是是完全二叉树”有过疑问,英特网也会有说不是一心二叉树的,不过无论堆是否完全二叉树,尚且保稳重见。大家假设知道,在那边大家选用完全二叉树情势的大根堆(小跟堆),紧若是为着便利存款和储蓄和总结(前边大家会看出带来的实惠)。

《高调数据结构》里的概念:堆
是怀有下列性质的通通二叉树:各种节点的值都大于或等于其左右亲骨血节点的值,成为大顶堆(大根堆);或许各样节点的值都低于或等于其左右节点的值,成为小顶堆(小根堆)。

二叉堆一般分为二种:最大堆和微小堆。
最大堆:
最大堆中的最大成分值出现在根结点(堆顶)
堆中每一个父节点的因素值都大于等于其子女结点(假设存在)

vnsc威尼斯城官方网站 16

登时自身在阅览这里的时候也对有“堆是还是不是是完全二叉树”有过难题,互连网也会有说不是完全二叉树的,不过无论堆是还是不是全然二叉树,尚且保留神见。大家假使知道,在此地大家运用完全二叉树格局的大根堆(小跟堆),重纵然为了便利存款和储蓄和总结(后边大家探望到带来的平价)。

vnsc威尼斯城官方网站 17

堆排序算法:

vnsc威尼斯城官方网站 18

(最大堆)
最小堆:
小小堆中的最小成分值出现在根结点(堆顶)
堆中每一个父节点的成分值都低于等于其儿女结点(倘诺存在)

堆排序就是选择堆(假设利用大根堆)举办排序的形式,它的基本思维是:将待排序的队列构形成多少个大根堆。此时,整个系列的最大值就是堆顶的根节点。将它移走(其实正是将其与堆数组的末梢成分调换,此时末尾成分正是最大值),然后将盈余的
n – 1 个连串重新布局成一个堆,那样就能够赢得 n
个因素中的次小的值。如此每每实行,便能获取贰个萧规曹随种类了。

堆排序算法:

vnsc威尼斯城官方网站 19

大根堆排序算法的基本操作:

堆排序正是接纳堆(假如利用大根堆)进行排序的诀窍,它的骨干思维是:将待排序的类别构形成三个大根堆。此时,整个连串的最大值正是堆顶的根节点。将它移走(其实正是将其与堆数组的末尾成分交流,此时末尾成分正是最大值),然后将剩余的
n – 1 个连串重新组织成三个堆,那样就能获得 n
个元素中的次小的值。如此一再实施,便能赢得叁个不变类别了。

(最小堆)
3. 堆排序原理 堆排序就是把最大堆堆顶的最大数抽出,将剩下的堆继续调节为最大堆,再次将堆顶的最大数抽取,那个进度不断到剩余数唯有贰个时停止。在堆中定义以下两种操作:
最大堆调度(马克斯-Heapify):将堆的背后子节点作调治,使得子节点永恒远小于父节点
创办最大堆(Build-马克斯-Heap):将堆全数数据再次排序,使其成为最大堆
堆排序(Heap-Sort):移除位在第二个数据的根节点,并做最大堆调解的递归运算
继续进行上面包车型地铁研讨前,必要留神的七个难点是:数组都是Zero-Based,那就代表大家的堆数据结构模型要发生转移

①建堆,建堆是延绵不断调治堆的长河,从 len/2
处最早调治,从来到第三个节点,此处 len
是堆凉月素的个数。建堆的进度是线性的进度,从 len/2 到 0
处向来调用调治堆的经过,约等于 o(h1) + o(h2) …+ o(hlen/2) 个中 h
表示节点的深浅, len/2 表示节点的个数,那是二个求和的进度,结果是线性的
O(n)。

大根堆排序算法的基本操作:

vnsc威尼斯城官方网站 20

②调动堆:调治堆在营造堆的经过中会用到,何况在堆排序进度中也会用到。利用的构思是相比较节点i和它的儿女节点
left(i) ,
right(i),选出三者最大(或然最小)者,借使最大(小)值不是节点i而是它的叁个儿女节点,那边彼此节点i和该节点,然后再调用调治堆进度,这是一个递归的历程。调治堆的历程时间复杂度与堆的深浅有提到,是
lgn 的操作,因为是本着深度方向扩充调治的。

①建堆,建堆是连连调解堆的长河,从
len/2 处先导调治,平昔到第多少个节点,此处 len
是堆霜月素的个数。建堆的经过是线性的经过,从 len/2 到 0
处一直调用调节堆的历程,也正是 o(h1) + o(h2) …+ o(hlen/2) 在那之中 h
表示节点的深浅, len/2 表示节点的个数,那是多少个求和的进度,结果是线性的
O(n)。

(Zero-Based)
相应的,多少个计算公式也要作出相应调度:
Parent(i) = floor((i-1)/2),i 的父节点下标
Left(i) = 2i + 1,i 的左子节点下标
Right(i) = 2(i + 1),i 的右子节点下标
最大堆调解(MAX‐HEAPIFY)的效率是保持最大堆的性质,是创设最大堆的主题子程序,功用进度如图所示:

③堆排序:堆排序是使用方面包车型地铁五个经过来拓宽的。首先是遵照成分营造堆。然后将堆的根节点抽出(一般是与终极一个节点开展置换),将前方
len-1
个节点继续展开堆调度的历程,然后再将根节点抽取,那样直接到持有节点都抽出。堆排序进程的岁月复杂度是
O(nlgn)。因为建堆的小时复杂度是 O(n)(调用贰回);调解堆的时间复杂度是
lgn,调用了 n-1 次,所以堆排序的时刻复杂度是 O(nlgn)。

②调动堆:调度堆在营造堆的经过中会用到,何况在堆排序过程中也会用到。利用的怀想是比较节点i和它的孩子节点
left(i) ,
right(i),选出三者最大(或然最小)者,假设最大(小)值不是节点i而是它的三个儿女节点,那边相互节点i和该节点,然后再调用调度堆过程,那是三个递归的经过。调节堆的历程时间复杂度与堆的纵深有提到,是
lgn 的操作,因为是本着深度方向扩充调节的。

vnsc威尼斯城官方网站 21

在这一个进度中是需求大批量的图示本领看的知情的,可是笔者懒。。。。。。

③堆排序:堆排序是行使方面包车型地铁四个经过来拓宽的。首先是依据成分创设堆。然后将堆的根节点收取(一般是与最后二个节点开展置换),将方今len-1
个节点继续张开堆调治的经过,然后再将根节点抽取,那样一直到全体节点都收取。堆排序进程的时光复杂度是
O(nlgn)。因为建堆的年华复杂度是 O(n)(调用贰次);调节堆的命宫复杂度是
lgn,调用了 n-1 次,所以堆排序的年月复杂度是 O(nlgn)。

(Max-Heapify)
鉴于一遍调节后,堆仍旧违反堆性质,所以供给递归的测量试验,使得全体堆都知足堆性质,用
JavaScript 能够象征如下:

算法达成:

在这么些进程中是索要多量的图示才具看的了然的,然而小编懒。。。。。。

/**
 * 从 index 开始检查并保持最大堆性质
 *
 * @array
 *
 * @index 检查的起始下标
 *
 * @heapSize 堆大小
 *
 **/
function maxHeapify(array, index, heapSize) {
 var iMax = index,
   iLeft = 2 * index + 1,
   iRight = 2 * (index + 1);

 if (iLeft < heapSize && array[index] < array[iLeft]) {
  iMax = iLeft;
 }

 if (iRight < heapSize && array[iMax] < array[iRight]) {
  iMax = iRight;
 }

 if (iMax != index) {
  swap(array, iMax, index);
  maxHeapify(array, iMax, heapSize); // 递归调整
 }
}

function swap(array, i, j) {
 var temp = array[i];
 array[i] = array[j];
 array[j] = temp;
}
<?php

//堆排序(对简单选择排序的改进)

function swap(array &$arr,$a,$b){
 $temp = $arr[$a];
 $arr[$a] = $arr[$b];
 $arr[$b] = $temp;
}

//调整 $arr[$start]的关键字,使$arr[$start]、$arr[$start+1]、、、$arr[$end]成为一个大根堆(根节点最大的完全二叉树)
//注意这里节点 s 的左右孩子是 2*s + 1 和 2*s+2 (数组开始下标为 0 时)
function HeapAdjust(array &$arr,$start,$end){
 $temp = $arr[$start];
 //沿关键字较大的孩子节点向下筛选
 //左右孩子计算(我这里数组开始下标识 0)
 //左孩子2 * $start + 1,右孩子2 * $start + 2
 for($j = 2 * $start + 1;$j <= $end;$j = 2 * $j + 1){
  if($j != $end && $arr[$j] < $arr[$j + 1]){
   $j ++; //转化为右孩子
  }
  if($temp >= $arr[$j]){
   break; //已经满足大根堆
  }
  //将根节点设置为子节点的较大值
  $arr[$start] = $arr[$j];
  //继续往下
  $start = $j;
 }
 $arr[$start] = $temp;
}

function HeapSort(array &$arr){
 $count = count($arr);
 //先将数组构造成大根堆(由于是完全二叉树,所以这里用floor($count/2)-1,下标小于或等于这数的节点都是有孩子的节点)
 for($i = floor($count / 2) - 1;$i >= 0;$i --){
  HeapAdjust($arr,$i,$count);
 }
 for($i = $count - 1;$i >= 0;$i --){
  //将堆顶元素与最后一个元素交换,获取到最大元素(交换后的最后一个元素),将最大元素放到数组末尾
  swap($arr,0,$i); 
  //经过交换,将最后一个元素(最大元素)脱离大根堆,并将未经排序的新树($arr[0...$i-1])重新调整为大根堆
  HeapAdjust($arr,0,$i - 1);
 }
}

$arr = array(9,1,5,8,3,7,4,6,2);
HeapSort($arr);
var_dump($arr);

算法完毕:

层出不穷来说,递归首要用在分治法中,而这边并无需分治。何况递归调用必要压栈/清栈,和迭代对待,品质上有略微的劣点。当然,依照20/80原理,那是足以忽略的。不过假如你感到用递归会让投机心里过不去的话,也得以用迭代,举个例子上面那样:

岁月复杂度深入分析:

<?php
//堆排序(对简单选择排序的改进)
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//调整 $arr[$start]的关键字,使$arr[$start]、$arr[$start+1]、、、$arr[$end]成为一个大根堆(根节点最大的完全二叉树)
//注意这里节点 s 的左右孩子是 2*s + 1 和 2*s+2 (数组开始下标为 0 时)
function HeapAdjust(array &$arr,$start,$end){
  $temp = $arr[$start];
  //沿关键字较大的孩子节点向下筛选
  //左右孩子计算(我这里数组开始下标识 0)
  //左孩子2 * $start + 1,右孩子2 * $start + 2
  for($j = 2 * $start + 1;$j <= $end;$j = 2 * $j + 1){
    if($j != $end && $arr[$j] < $arr[$j + 1]){
      $j ++; //转化为右孩子
    }
    if($temp >= $arr[$j]){
      break; //已经满足大根堆
    }
    //将根节点设置为子节点的较大值
    $arr[$start] = $arr[$j];
    //继续往下
    $start = $j;
  }
  $arr[$start] = $temp;
}
function HeapSort(array &$arr){
  $count = count($arr);
  //先将数组构造成大根堆(由于是完全二叉树,所以这里用floor($count/2)-1,下标小于或等于这数的节点都是有孩子的节点)
  for($i = floor($count / 2) - 1;$i >= 0;$i --){
    HeapAdjust($arr,$i,$count);
  }
  for($i = $count - 1;$i >= 0;$i --){
    //将堆顶元素与最后一个元素交换,获取到最大元素(交换后的最后一个元素),将最大元素放到数组末尾
    swap($arr,0,$i);
    //经过交换,将最后一个元素(最大元素)脱离大根堆,并将未经排序的新树($arr[0...$i-1])重新调整为大根堆
    HeapAdjust($arr,0,$i - 1);
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
HeapSort($arr);
var_dump($arr);
/**
 * 从 index 开始检查并保持最大堆性质
 *
 * @array
 *
 * @index 检查的起始下标
 *
 * @heapSize 堆大小
 *
 **/
function maxHeapify(array, index, heapSize) {
 var iMax, iLeft, iRight;
 while (true) {
  iMax = index;
  iLeft = 2 * index + 1;
  iRight = 2 * (index + 1);
  if (iLeft < heapSize && array[index] < array[iLeft]) {
   iMax = iLeft;
  }

  if (iRight < heapSize && array[iMax] < array[iRight]) {
   iMax = iRight;
  }

  if (iMax != index) {
   swap(array, iMax, index);
   index = iMax;
  } else {
   break;
  }
 }
}

function swap(array, i, j) {
 var temp = array[i];
 array[i] = array[j];
 array[j] = temp;
}

它的周转时刻一旦是消耗在初步创设对和在重新创设堆屎的再三筛选上。

运作结果:

创制最大堆(Build-马克斯-Heap)的功效是将二个数组退换成二个最大堆,接受数组和堆大小四个参数,Build-马克斯-Heap
将自下而上的调用 马克斯-Heapify 来改变数组,建构最大堆。因为 马克斯-Heapify
能够确定保障下标 i 的结点之后结点都知足最大堆的品质,所以自下而上的调用
马克斯-Heapify 可以在更换进程中保障这一质量。若是最大堆的数量成分是 n,那么
Build-马克斯-Heap 从 Parent(n) 开首,往上各类调用 马克斯-Heapify。流程如下:

完整上的话,堆排序的时刻复杂度是
O(nlogn)。由于堆排序对原始记录的排序状态并不灵动,因而它不管最佳、最差和平均时间复杂度都以O(nlogn)。那在质量上旗帜明显要远远好于冒泡、轻易选取、间接插入的 O(n^2)
的年华复杂度了。

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

vnsc威尼斯城官方网站 22

堆排序是一种不平静排序方法。

日子复杂度剖判:

用 JavaScript 描述如下:

本篇博客参谋自《大话数据结构》,在此仅作记录,方便未来翻看,大神勿喷!

它的运作时刻要是是消耗在开班营造对和在重新建构堆屎的一再筛选上。

function buildMaxHeap(array, heapSize) {
 var i,
   iParent = Math.floor((heapSize - 1) / 2);

 for (i = iParent; i >= 0; i--) {
  maxHeapify(array, i, heapSize);
 }
}

您或然感兴趣的篇章:

  • PHP实现的堆排序算法详解
  • php堆排序达成原理与行使措施
  • php堆排序(heapsort)练习
  • PHP排序算法之Hill排序(Shell
    Sort)实例剖判
  • PHP排序算法之直接插入排序(Straight Insertion
    Sort)实例深入分析
  • PHP排序算法之大概选取排序(Simple Selection
    Sort)实例深入分析
  • PHP排序算法之冒泡排序(Bubble
    Sort)完成格局详解
  • PHP 神速排序算法详解
  • PHP 冒泡排序算法的贯彻代码
  • php完结的广大排序算法汇总
  • PHP排序算法之堆排序(Heap
    Sort)实例详解

一体化上的话,堆排序的时间复杂度是 O(nlogn)。由于堆排序对原始记录的排序状态并不灵活,由此它不管最佳、最差和平均时间复杂度皆以O(nlogn)。这在品质上醒目要远远好于冒泡、轻巧选拔、直接插入的
O(n^2) 的时光复杂度了。

堆排序(Heap-Sort)是堆排序的接口算法,Heap-Sort先调用Build-马克斯-Heap将数组改造为最大堆,然后将堆顶和堆底成分沟通,之后将尾部上升,末了再一次调用马克斯-Heapify保持最大堆性质。由于堆顶成分必然是堆中最大的成分,所以三遍操作之后,堆中存在的最大意素被分别出堆,重复n-1次未来,数组排列实现。整个流程如下:

堆排序是一种不安静排序方法。

vnsc威尼斯城官方网站 23

用 JavaScript 描述如下:

function heapSort(array, heapSize) {

 buildMaxHeap(array, heapSize);

 for (int i = heapSize - 1; i > 0; i--) {
  swap(array, 0, i);
  maxHeapify(array, 0, i);
 } 
}

4.JavaScript 语言完毕 最后,把上边的股价整理为总体的 javascript 代码如下:

function heapSort(array) {

 function swap(array, i, j) {
  var temp = array[i];
  array[i] = array[j];
  array[j] = temp;
 }

 function maxHeapify(array, index, heapSize) {
  var iMax,
   iLeft,
   iRight;
  while (true) {
   iMax = index;
   iLeft = 2 * index + 1;
   iRight = 2 * (index + 1);

   if (iLeft < heapSize && array[index] < array[iLeft]) {
    iMax = iLeft;
   }

   if (iRight < heapSize && array[iMax] < array[iRight]) {
    iMax = iRight;
   }

   if (iMax != index) {
    swap(array, iMax, index);
    index = iMax;
   } else {
    break;
   }
  }
 }

 function buildMaxHeap(array) {
  var i,
   iParent = Math.floor(array.length / 2) - 1;

  for (i = iParent; i >= 0; i--) {
   maxHeapify(array, i, array.length);
  }
 }

 function sort(array) {
  buildMaxHeap(array);

  for (var i = array.length - 1; i > 0; i--) {
   swap(array, 0, i);
   maxHeapify(array, 0, i);
  }
  return array;
 }

 return sort(array);
}

5.堆排序算法的利用

(1)算法品质/复杂度 堆排序的年月复杂度非常平静(我们能够见到,对输入数据不灵动),为O(n㏒n)复杂度,最棒状态与最坏情状同样。
只是,其空间复杂度依完结分裂而差异。上边即钻探了三种广泛的复杂度:O(n)与O(1)。本着节约空间的标准,笔者推荐O(1)复杂度的艺术。

(2)算法牢固性 堆排序存在大气的筛选和活动进程,属于动荡的排序算法。

(3)算法适用场景 堆排序在创造堆和调动堆的进程中会产生相当大的花费,在要素少的时候并不适用。不过,在要素非常多的状态下,依旧不错的一个取舍。越发是在消除诸如“前n大的数”一类难题时,大概是首荐算法。

您或然感兴趣的篇章:

  • C语言选择排序算法及实例代码
  • 轻易精通桶排序算法及C++版的代码达成
  • 详解Bucket
    Sort桶排序算法及C++代码完成示例
  • 深远深入分析Radix
    Sort基数排序算法观念及C语言达成示例
  • 详解桶排序算法的笔触及C++编制程序中的代码达成
  • 桶排序算法的知晓及C语言版代码示例
  • Objective-C达成冒泡排序算法的简易示例
  • 解读堆排序算法及用C++达成基于最大堆的堆排序示例
  • JavaScriptHill排序、快速排序、归并排序算法
  • C/C++完成八大排序算法汇总

相关文章