徐旭 的个人博客

二叉堆与堆排序

二叉堆是一组能够用堆有序的完全二叉树排序的元素,一般用数组来存储。

大顶堆, 每个结点的值都大于或等于其左右孩子结点的值,其顶部为最大值。

小顶堆,每个结点的值都小于或等于其左右孩子结点的值,其顶部为最小值。

二叉堆

性质

  • 根节点在数组中的位置是 1
    • 左边子节点 2i
    • 右子节点 2i+1
    • 父节点 i / 2
    • 最后一个非叶子节点为 len / 2
  • 根节点在数组中的位置是 0
  • 左子节点 2i + 1
  • 右边子节点 2i+ 2
  • 父节点的下标是 (i − 1) / 2
  • 最后一个非叶子节点为 len / 2 - 1

图片来自知乎

实现

构造二叉堆

  • 找到最后一个非叶子节点 ( len / 2 或者 len / 2 - 1)
  • 从最后一个非叶子节点下标索引开始递减,逐个下沉

插入节点

  • 在数组的最末尾插入新节点
  • 将最后一个节点上浮,时间复杂度为O(log n)
    • 比较当前节点与父节点
    • 不满足 堆性质* *则交换

删除根节点

删除根节点用于堆排序

对于最大堆,删除根节点就是删除最大值;

对于最小堆,是删除最小值。

  • 交换根节点和最后一个节点
  • 将此时的根节点下沉,时间复杂度为O(log n)
    • 比较当前节点与子节点(左,右)
    • 不满足 堆性质 则交换
  • 删除最后一个节点

代码

https://github.com/Allenxuxu/dsa/blob/master/heap/heap.go

代码 来源 go 标准库 ,少量修改提高可读性

package heap


import "sort"


type Interface interface {
   sort.Interface
   Push(x interface{}) // add x as element Len()
   Pop() interface{}   // remove and return element Len() - 1.
}


// Init establishes the heap invariants required by the other routines in this package.
// Init is idempotent with respect to the heap invariants
// and may be called whenever the heap invariants may have been invalidated.
// The complexity is O(n) where n = h.Len().
func Init(h Interface) {
   // heapify
   n := h.Len()
   for i := n/2 - 1; i >= 0; i-- {
      down(h, i, n)
   }
}


// Push pushes the element x onto the heap.
// The complexity is O(log n) where n = h.Len().
func Push(h Interface, x interface{}) {
   h.Push(x)
   up(h, h.Len()-1)
}


// Pop removes and returns the minimum element (according to Less) from the heap.
// The complexity is O(log n) where n = h.Len().
// Pop is equivalent to Remove(h, 0).
func Pop(h Interface) interface{} {
   n := h.Len() - 1
   h.Swap(0, n)
   down(h, 0, n)
   return h.Pop()
}


// Remove removes and returns the element at index i from the heap.
// The complexity is O(log n) where n = h.Len().
func Remove(h Interface, i int) interface{} {
   n := h.Len() - 1
   if n != i {
      h.Swap(i, n)
      // 如果此节点不需要下沉,则尝试上浮
      if !down(h, i, n) {
         up(h, i)
      }
   }
   return h.Pop()
}


// Fix re-establishes the heap ordering after the element at index i has changed its value.
// Changing the value of the element at index i and then calling Fix is equivalent to,
// but less expensive than, calling Remove(h, i) followed by a Push of the new value.
// The complexity is O(log n) where n = h.Len().
func Fix(h Interface, i int) {
   if !down(h, i, h.Len()) {
      up(h, i)
   }
}


func up(h Interface, j int) {
   for {
      parent := (j - 1) / 2
      if parent == j || h.Less(parent, j) {
         break
      }
      h.Swap(parent, j)
      j = parent
   }
}


func down(h Interface, i0, n int) bool {
   i := i0
   for {
      left := 2*i + 1
      if left >= n || left < 0 { // j1 < 0 after int overflow
         break
      }


      toCompare := left // left child
      if right := left + 1; right < n && h.Less(right, left) {
         // 如果右节点比左节点小,则直接用右节点去比较
         toCompare = right // = 2*i + 2  // right child
      }
      if h.Less(i, toCompare) {
         break
      }
      h.Swap(i, toCompare)
      i = toCompare
   }
   return

堆排序

堆排序是借助“堆”这种数据结构进行排序的排序算法。

实现

  • 将原数组构造成堆
  • 将堆顶元素和数组最后一个元素交换,然后执行下沉操作修复堆(此时修复的堆长度-1,最后一个元素用来存放有序数据)
  • 重复上述步骤,直至堆为空

代码

https://github.com/Allenxuxu/dsa/blob/master/sort/heapsort.go

type Interface interface {
   // Len is the number of elements in the collection.
   Len() int
   // Less reports whether the element with
   // index i should sort before the element with index j.
   Less(i, j int) bool
   // Swap swaps the elements with indexes i and j.
   Swap(i, j int)
}


func down(data Interface, root, n int) {
   for {
      child := 2*root + 1 // left child
      if child >= n {
         break
      }
      if child+1 < n && data.Less(child, child+1) {
         // right = child+1
         child++
      }
      if data.Less(child, root) {
         return
      }
      data.Swap(root, child)
      root = child
   }
}


func HeapSort(data Interface) {
   n := data.Len()
   // Build heap with greatest element at top.
   for i := n/2 - 1; i >= 0; i-- {
      down(data, i, n)
   }


   // Pop elements, largest first, into end of data.
   for i := n - 1; i >= 0; i-- {
      data.Swap(0, i)
      down(data, 0, i)
   }

应用

堆排序是唯一能够同时最优化的利用空间和时间的方法 -- 在最坏的情况下也能保证使用 2NlogN 次比较和恒定额外空间。

但是,现代系统中许多应用很少使用它,因为它无法利用缓存 -- 数组元素很少和相邻的元素进行比较。因此缓存命中次数远低于在相邻元素进行比较的算法,如快速排序,归并排序,甚至是希尔排序。


标题:二叉堆与堆排序
作者:Allenxuxu
地址:https://mogutou.xyz/articles/2020/05/30/1590811456517.html
Github: https://github.com/Allenxuxu
转载请注明出处