图文详解Heap Sort堆排序算法及JavaScript的代码实现

标签:行业资讯    日期:2018-01-30 11:49    录入:天恒娱乐平台注册    浏览:

  

[堆排序算法,JavaScript,js,堆排序,排序算法]图文详解Heap Sort堆排序算法及JavaScript的代码实现

  

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 个节点称之为满二叉树  
  

  

201654180037749.png (325×199)  

  

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

  

201654180205013.png (298×198)  

  

(深度为 3 的完全二叉树 complete binary tree)  
  2. 什么是堆?

  
  
堆(二叉堆)可以视为一棵完全的二叉树,完全二叉树的一个“优秀”的性质是,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示(普通的一般的二叉树通常用链表作为基本容器表示),每一个结点对应数组中的一个元素。

  
  如下图,是一个堆和数组的相互关系  
  

  

201654180403849.png (564×182)  

  

(堆和数组的相互关系)  
  对于给定的某个结点的下标 i,可以很容易的计算出这个结点的父结点、孩子结点的下标:  
  Parent(i) = floor(i/2),i 的父节点下标  
  Left(i) = 2i,i 的左子节点下标  
  Right(i) = 2i + 1,i 的右子节点下标  
  

  

201654180531505.png (549×172)  

  

  

  

二叉堆一般分为两种:最大堆和最小堆。

  
  最大堆:  
  最大堆中的最大元素值出现在根结点(堆顶)  
  堆中每个父节点的元素值都大于等于其孩子结点(如果存在)  
  

  

201654180552874.png (373×112)  

  

(最大堆)  
  最小堆:  
  最小堆中的最小元素值出现在根结点(堆顶)  
  堆中每个父节点的元素值都小于等于其孩子结点(如果存在)  
  

  

201654180607921.png (370×112)  

  

(最小堆)  
  3. 堆排序原理  
  
堆排序就是把最大堆堆顶的最大数取出,将剩余的堆继续调整为最大堆,再次将堆顶的最大数取出,这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作:  
  最大堆调整(Max-Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点  
  创建最大堆(Build-Max-Heap):将堆所有数据重新排序,使其成为最大堆  
  堆排序(Heap-Sort):移除位在第一个数据的根节点,并做最大堆调整的递归运算  
  继续进行下面的讨论前,需要注意的一个问题是:数组都是 Zero-Based,这就意味着我们的堆数据结构模型要发生改变  
  

  

201654180627211.png (562×194)  

  

(Zero-Based)  
  相应的,几个计算公式也要作出相应调整:  
  Parent(i) = floor((i-1)/2),i 的父节点下标  

★★★小编:天恒娱乐 整理文章,欢迎大家转载 ★★★
上一篇:jquery交替变换颜色的三种方法 实例代码
下一篇:没有了