当前位置: 代码迷 >> 综合 >> 堆 数据结构(Heap)-scala代码实现
  详细解决方案

堆 数据结构(Heap)-scala代码实现

热度:40   发布时间:2024-01-16 02:14:59.0
package com.datastructureimport scala.util.control._object Heap {//建堆def apply(MaxSize: Int) = {/* 创建容量为MaxSize的空的最大堆 */val H = new Heap(MaxSize)/* 定义"哨兵"为大于堆中所有可能元素的值*/H.Data(0) = 1000H}
}class Heap(MaxSize: Int) {private var Data = new Array[Int](MaxSize + 1) // 存储元素的数组private var Size: Int = 0 // 堆中当前元素个数private var Capacity: Int = MaxSize // 堆的最大容量//打印堆中元素def showHeap: Unit = {for (indx <- 1 to Size) {println(Data(indx))}}//判断 堆满def isFull = {Size == Capacity}//判断 堆空def isEmpty = {Size == 0}//往堆中插入数据def insert(x: Int) {/* 将元素X插入最大堆H,其中H->Data[0]已经定义为哨兵 */if (isFull) {println("最大堆已满,插入失败!");return}var i = Size + 1; /* i指向插入后堆中的最后一个元素的位置 */while (Data(i / 2) < x) {Data(i) = Data(i / 2)i /= 2}Data(i) = xSize += 1println(s"插入成功,位置为$i");}//删除最大值 重点在调整(为最后一个元素找个新地址 ,但是需要从上往下调整)def deleteMax {/* 从最大堆H中取出键值为最大的元素,并删除一个结点 */if (isEmpty) {println("最大堆已空,删除失败!");return}val MaxElem = Data(1)val x = Data(Size)Size -= 1var parent: Int = 1var child: Int = parent * 2 //指向左右孩子中较大的那个,默认给左孩子// 创建 Breaks 对象val loop = new Breaks;loop.breakable {while (child <= Size) { //从根节点的左右孩子找出一个最大的,替换根节点,然后递归层层下滤if (child != Size && Data(child) < Data(child + 1)) {child += 1}if (x >= Data(child)) /* 找到了合适位置 */ {loop.break}else /* 下滤X */ {Data(parent) = Data(child)parent = childchild = parent * 2}}}Data(parent) = xprintln(s"删除$MaxElem");}
}
  相关解决方案