二叉堆与Top-K问题 yinshibanxian

一、什么是二叉堆

二叉堆是一种特殊的二叉树,有以下两个特性:

  • 二叉堆是一棵完全二叉树,表示树的每一层都有左节点和右节点(除了最后一层的叶子节点),并且最后一层的叶节点尽可能都是左节点 这叫做结构特性。
  • 二叉堆不是最小堆就是最大堆。最小堆允许快速导出树的最小值,最大堆允许快速导出树的最大值。所有的节点都大于等于(最大堆)或 小于等于(最小堆)特的每个子节点,这叫做堆特性。

下面是一些合法的和不合法的堆:

image

#### 二、创建最小堆

1. 二叉树的数组表示

因为我们要用二叉堆来解决Top-K问题,所以我们需要采用数组来表示二叉树。二叉树有两种表示方式,

一种是使用一个动态的方式,也就是指针(用节点表示)。第二种则是用使用一个数组,通过索引值检索

父节点、左侧和右侧子节点的值。下图展示了二叉树的两种表示方法:

image

在用数组表示的二叉树中,对于给定位置index的节点:

  • 它的左侧子节点的位置是2*index+1(如果该位置可用)
  • 它的右侧子节点的位置是2*index+2(如果该位置可用)
  • 它的父节点的位置是Math.floor((index - 1) / 2)(如果该位置可用)

2. 创建一个最小堆类

 class MinHeap {
     
 }