二叉树与堆排序
Oct242018
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 | 边城网事