数据结构与算法（三）二叉堆和优先队列——会自动排序的队列

png/B220micXXwOMicso6BC5EKmOIia4h4G7XhSsNzSn5Be2VjDlbIGzR98NmNNuMw7SkqrgG0KeesfMtCSTpEnXelTlQ/640?wx_fmt=png)

2、父节点的值总是小于等于左右子节点的值

3、插入和删除一个节点时能够自动调节树，使其永远满足第二点

二叉堆的操作（以升序的最小堆为例）

1、插入节点

插入节点永远是插入到最后一个节点并通过上浮操作到达合适的位置，过程如下所示：

2、删除节点

二叉堆只能删除根节点（一般不会删除非根节点外的节点），当根节点被删后，会把最后一个节点放到根节点上占位，再将根节点下沉到它正确的位置

3、** **构建二叉堆

构建二叉堆需要先构建一个无序的完全二叉树，再从最后一个有子节点的节点（即最后一个非叶子节点）开始，从下往上的对一个个节点依次做下沉操作。

例如上图这个无序二叉树，需要依次对10,3,1,7这几个节点做下沉操作。

上浮和下沉的最大交换次数是树的层数，我们知道树的层数约等于树节点数量的取对数，所以上浮和下沉的复杂度是O(logn)。

二叉堆的构建需要对每个非叶子节点做下沉操作，每个下沉操作为O(logn)，表面看构建二叉堆的复杂度为O(nlogn)，然而实际上全部节点下沉的整体复杂度是O(n)。

二叉堆一般使用顺序存储的数组作为底层结构。假设父节点的下标是parent，那么它的左孩子下标就是 2×parent+1；右孩子下标就是2×parent+2

下面是二叉堆的实现：

// 二叉堆type Heap []int
// 最小堆上浮操作func UpAdjust(heap Heap){  childIdx := len(heap) - 1  parentIdx := (childIdx - 1) / 2   // 除成小数会向下取整  temp := heap[childIdx]        // 临时变量记录要上浮的节点的值
  for childIdx > 0 && temp < heap[parentIdx]{    // 不要写成heap[childIdx] < heap[parentIdx]    heap[childIdx] = heap[parentIdx]    childIdx = parentIdx    parentIdx = (childIdx - 1) / 2  }  heap[childIdx] = temp}
// 最小堆下沉操作func DownAdjust(heap Heap, idx int){  // 对指定下标的节点下沉  if idx + 1 > len(heap){    // 超出范围的下标    return  }
  parentIdx := idx  childIdx := parentIdx * 2 + 1  // 默认要替换的子节点取左节点  temp := heap[parentIdx]
  for childIdx <= len(heap) - 1{  // 如果节点还没有下沉到超过堆长度的位置就可以继续做下沉操作    // 取左右子节点中小的那个节点与temp比较    if childIdx + 1 <= len(heap) - 1 && heap[childIdx] > heap[childIdx + 1]{      childIdx++    }
    if temp <= heap[childIdx]{      break    }    heap[parentIdx] = heap[childIdx]    parentIdx = childIdx    childIdx = parentIdx * 2 + 1  }  heap[parentIdx] = temp  // 不要写成heap[parentIdx] = temp，不然会超出数组范围}
// 下沉到指定下标操作func DownAdjustToLastIdx(heap Heap, idx, lastIdx int){  // 对指定下标的节点下沉  if idx + 1 > len(heap){    // 超出范围的下标    return  }
  parentIdx := idx  childIdx := parentIdx * 2 + 1  // 默认要替换的子节点取左节点  temp := heap[parentIdx]
  for childIdx <= lastIdx{  // 如果节点还没有下沉到超过堆长度的位置就可以继续做下沉操作    // 如果有右节点而且右节点小于左节点，则取左节点替换    if childIdx + 1 <= lastIdx && heap[childIdx] > heap[childIdx + 1]{      childIdx++    }
    if temp <= heap[childIdx]{      break    }    heap[parentIdx] = heap[childIdx]    parentIdx = childIdx    childIdx = parentIdx * 2 + 1  }  heap[parentIdx] = temp  // 不要写成heap[parentIdx] = temp，不然会超出数组范围}
// 构建最小二叉堆func BuildHeap(arr []int) (heap Heap){  heap = (Heap)(arr)  lastIdx := (len(heap) - 2) / 2    // 最后一个节点下标
  for idx := lastIdx; idx >= 0; idx--{    DownAdjust(heap, idx)  }
  return heap}

02 优先队列

优先队列的定义是，往某个队列的队尾插入任意无序的元素后，可以从队首有序的弹出所有元素，这样的队列就是优先队列。

有意思的是，优先队列并不是一个有序的队列，但是将元素出列时是有序的出列。原因是优先队列逻辑上并不是一个线性数据结构，而是一个树形结构。

优先队列就是通过上面所说的二叉堆实现的，或者说优先队列就是一个二叉堆。

当有元素入列时，该元素会先进入队列尾部，并上浮到合适的位置。

当有元素出列时，实际上是获取堆顶（二叉堆的根节点）元素，该元素会被最后一个元素（最后一个叶子节点）替换，并下沉到合适的位置。

所以优先队列入列和出列的复杂度为O(logn)

下面是优先队列的代码实现

// (最小)优先队列
func InitPriorityQueue() *Heap{  pq := make(Heap, 0, 32)  // 队列初始容量为32  return &pq}
// 入列func EnQueue(pq *Heap, ele int){  *pq = append(*pq, ele)  UpAdjust(*pq)}
// 出列func DeQueue(pq *Heap) (target int){  if len(*pq) == 0{    panic("priority empty！")  }  target = (*pq)[0]
  // 切片的最后一个元素放到第一个元素  (*pq)[0] = (*pq)[len(*pq) - 1]
  //再删除最后一个元素，切片的len会自动-1  *pq = (*pq)[:len(*pq) - 1]
  // 对根节点做下沉操作  DownAdjust(*pq, 0)
  return target}