前言

写了一个小例子，理解下创建堆和堆排序的过程。记录下，方便以后复习。直接上源码吧，注释比较详细。如有问题，希望各位大佬指正
import scala.collection.mutable.ArrayBuffer
import scala.util.control.Breaks.{break, breakable}

object Heap {

  def main(args: Array[String]): Unit = {
    // 任意创建一个数组
    val arr = Array(2,8)

    arr.foreach(x => print(x + " "))

    println()

    // 创建堆
    val heap = build_heap(arr)

    heap.foreach(x => print(x + " "))

    println()

    // 堆排序
    val sorted = heap_sort(heap)

    sorted.foreach(x => print(x + " "))
  }

  def build_heap(arr: Array[Int]):Array[Int] = {
    val heap = new ArrayBuffer[Int]()

    for(item <- arr) {
      // 添加元素至堆尾，此时有可能破坏堆的结构，会进行堆尾首元素进行上浮操作
      heap.append(item)
      // 堆尾元素上浮
      siftUp(heap, heap.size - 1)
    }
    heap.toArray
  }

  def heap_sort(heap: Array[Int]): Array[Int] = {
    // 新建一个数组，存储最终的有序结果
    val sortedArr = new ArrayBuffer[Int]()

    var lastItemIndex = heap.size - 1

    // 遍历堆
    while (lastItemIndex >= 0){
      // 每次取出堆顶元素
      sortedArr.append(heap(0))
      // 将堆顶元素调整至队首，此时有可能破坏堆的结构，需将堆顶元素进行下沉操作
      heap(0) = heap(lastItemIndex)
      // 将堆尾元素置位无用元素，用-1标记
      heap(lastItemIndex) = -1
      lastItemIndex = lastItemIndex - 1
      // 堆顶元素进行下沉
      siftDwon(heap, 0, lastItemIndex)
    }
    sortedArr.toArray
  }

  def siftUp(heap: ArrayBuffer[Int], index: Int) = {

    var k = index
    val item = heap(k)

    breakable {
      while (k > 0) {
        // 父节点
        val parent = (k - 1 ) >>> 1   // 完全二叉树父子节点索引关系: left child = 2 * parent + 1

        // 大顶堆。如果父节点大于待上浮元素，则不用上浮，跳出循环
        if(heap(parent) >= item)  break

        // 如果如果父节点小于待上浮元素，则父元素下沉
        heap(k) = heap(parent)

        // 调整待上浮位置，进行下一次上浮试探
        k = parent
      }
    }

    heap(k) = item
  }


  /*
  heap: 堆对象, 数组类型
  index: 进行下沉操作的元素的索引位置
  size: heap中实际存储的元素个数
   */
  def siftDwon(heap: Array[Int], index: Int, size: Int) = {

    var k = index
    val stop = size >>> 1
    val item = heap(index)

    breakable {
      while (k <= stop) {
        // 左子节点
        val left = 2 * k + 1
        // 右子节点
        val right = 2 * k + 2

        // 85~88行，获取左右子节点中较大的元素
        var c = left
        if(right <= size && heap(left) < heap(right)) {
          c = right
        }

        // 大顶堆。如果待下沉元素大于子节点，则不用下沉，跳出循环
        if(item >= heap(c)) break

        // 子节点中较大元素上浮
        heap(k) = heap(c)

        // 调整待下沉位置，进行下一次下沉试探
        k = c
      }
    }

    // 找到合适下沉位置
    heap(k) = item
  }
}
堆排序小demo

前言
