当前位置: 首页 > Scala, 算法 > 正文

二叉树与堆排序

package com.alg.test

/**
  * ****************************   二叉树与堆排序  ********************************
  * 最近工作中,需要用到树的相关数据结构和算法,正好前段时间收了一本数据结构和算法相关的书,就看了下树相关的章节.
  * 记录作为读书笔记,加深理解,也便于以后复习
  *
  * 1 - 概念:
  *   1.1 二叉树, 二叉树要么为空,要么由根节点,左子树和右子树组成,而左子树,右子树也分别都是一颗二叉树
  *   1.2 满二叉树,二叉树每个内部节点都有两个儿子,这样的二叉树叫做满二叉树
  *   1.3 完全二叉树,若设二叉树的高度为h,除了第h层外,其他各层(1~h-1)层的节点数都达到最大,第h层从右向左连续缺失若干节点,
  *       则这个二叉树是完全二叉树.
  *   1.4 最小堆, 完全二叉树,所有的父节点都比子节点要小,这样的完全二叉树称为最小堆
  *
  * 2 - 性质
  *   2.1 将完全二叉树进行自上而下,从左到右编号,那么只需要用一个一维数组就可以存储完全二叉树
  *   2.2 如果完全二叉树的一个父节点编号为k, 那么它的左儿子编号为2*k,右儿子编号为2*k+1
  *   2.3 如果已知儿子(左儿子或者右儿子)的编号是x,那么它父节点的编号为x/2(注意这里是整出,取商,不包含小数部分)
  *
  * 利用上述概念和性质,可以将任意一个整数数组规整为一个最小堆,然后取堆顶元素,则该元素为最小值,
  * 将堆剩下的部分再次规整为一个最小堆,再次取堆顶元素,依次类推,就可以堆一个整数数组进行升序排序了.
  *
  * TODO 二叉树的 前序、中序和后序 遍历
  */
object TestTree {
  def main(args: Array[String]): Unit = {
    var h = collection.mutable.ArraySeq(99, 5, 36, 7, 22, 17, 46, 12, 2, 19, 25, 28, 1, 92)

    (1 to h.size).foreach(i => {
        createHeap(h)  //构造最小堆
        print(h(0) + " ") //取出堆顶的最小元素
        h = h.slice(1,h.size) //剩下元素再次构造最小堆,以此类推
      }
    )

    println(h.mkString(","))

  }

  /**
    * 向下调整二叉树, 每一个非叶子节点,跟其左右子节点比较,将较小的值交换上来作为根节点,
    * 一直到不需要交换为止(由根节点开始,由上而下,较小的数在上面)
    *
    * @param aSeq Seq 形式保存的二叉树
    * @param i    二叉树的节点编号,从1开始的,注意上面的Seq编号从0开始
    */
  def siftDown(aSeq: collection.mutable.ArraySeq[Int], i: Int): Unit = { //i 节点编号,从1 开始
    val totalCount = aSeq.size
    var stopSwitchFlag = 0

    var smallerValueIndex = i // 记录当前较小的节点编号,从1开始
    var currentIndex = i
    //完全二叉树,最后一个非叶子节点的编号为 n / 2, n为节点总数(啊哈算法 p192)
    while (currentIndex * 2 <= totalCount && stopSwitchFlag == 0) {
      //判断当前节点和左节点的关系, 当前非叶子节点肯定有左节点
      if (aSeq(currentIndex - 1) < aSeq(currentIndex * 2 - 1)) {
        smallerValueIndex = currentIndex * 2 //左节点编号
      } else {
        smallerValueIndex = currentIndex
      }

      //判断有没有右节点
      if (currentIndex * 2 + 1 <= totalCount) {
        //有右节点 再比较当前节点和右节点的大小,记录数值较小的节点编号
        if (aSeq(smallerValueIndex - 1) < aSeq(currentIndex * 2)) {
          smallerValueIndex = currentIndex * 2 + 1 //右节点编号
        }
      }

      //如果发现最小的节点编号不是当前编号,说明子节点中有比父节点更小的
      if (smallerValueIndex != currentIndex) {
        switchValue(aSeq, currentIndex - 1, smallerValueIndex - 1)
        currentIndex = smallerValueIndex //更新当前节点编号为较小数值得子节点编号,便于再交换改子节点的子节点
      } else {
        stopSwitchFlag = 1
      }
    }
  }

  def switchValue(aSeq: collection.mutable.ArraySeq[Int], i: Int, j: Int): Unit = {
    val t = aSeq(i)
    aSeq(i) = aSeq(j)
    aSeq(j) = t
  }

  /**
    * 给定一个初始的Seq,该函数将这个Seq调整成一个最小堆: 即一个根节点为最小值,并且左节点小于右节点的完全二叉树,
    * 该二叉树存储在这个Seq中
    *
    * @param aSeq
    */
  def createHeap(aSeq: collection.mutable.ArraySeq[Int]): Unit = {
    val size = aSeq.size
    val lastNoneLeafIndex = size / 2
    val indexes = (1 to lastNoneLeafIndex).reverse
    indexes.foreach((i: Int) => {
      siftDown(aSeq, i)
    })
  }
}
赞 赏

   微信赞赏  支付宝赞赏


本文固定链接: https://www.jack-yin.com/coding/scala/2725.html | 边城网事

该日志由 边城网事 于2018年10月24日发表在 Scala, 算法 分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
原创文章转载请注明: 二叉树与堆排序 | 边城网事

二叉树与堆排序 暂无评论

发表评论

快捷键:Ctrl+Enter