第十一章二叉堆 / 开普饭

简介

二叉堆是一种特殊的二叉树,但是不是一个二叉搜索树,二叉堆 是计算机科学中非常著名的数据结构,又称堆,由于其高效,快速地查找出最大值和最小值,常用于优先队列

结构

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

尽管二叉堆是二叉树,但并不一定是二叉搜索树(BST).在二叉堆中,每个子节点都要大于等于父节点(最小堆)或小于等于父节点(最大堆).然而二叉搜索树中,左侧子节点总是比父节点小,右侧子节点也总是更大

创建我们的最小堆

选择存储数据的数据类型

这里可以选择和上一章树一样的数据类型(双指针,一个左指针,一个右指针),但是也可以使用数组

左节点: 当前节点下标 * 2 + 1

右节点:当前节点下标 * 2 + 2

父节点: (index - 1) / 2 (当位置可用时,这是一个边界,注意 )

基础方法

insert(value) : 这个方法向堆中插入一个新的值.如果插入成功,它返回true,否则返回false

extract(): 这个方法移除最小值(最小堆的时候)或最大值(最大堆的时候),并返回这个值

findMinimum():这个方法返回最小值(最小堆的时候)或最大值(最大堆的时候),但不会删除该值

基础方法

enum Compare {
  LESS_THAN = -1,
  BIGGER_THAN = 1,
  EQUALS = 0
}

function defaultCompareFn<T>(parent: T, child: T) {
  if (parent === child) {
    return Compare.EQUALS
  }
  return parent > child ? Compare.BIGGER_THAN : Compare.LESS_THAN;
}
// 数组交换
function swap<T>(array: Array<T>, index: number, otherIndex: number) {
  [array[index], array[otherIndex]] = [array[otherIndex], array[index]];
}

这里添加一个枚举类型,表示小于,大于,等于

添加一个默认比较方法

添加一个数组交换的方法,因为经常要进行数组交换

基础结构

export class MinHeap<T> {
  private heap: Array<T>;
  compareFn: Function;

  constructor(compareFn: Function = defaultCompareFn) {
    //使用数组一定程度上不用去维护左右的指针
    this.heap = [];
    //这个是一个比较大小的方法,与前面类似
    this.compareFn = compareFn;
  } 

  //获取左边子元素位置
  getLeftIndex(index: number) {
    return index * 2 + 1;
  }

  //获取右边子元素位置
  getRightIndex(index: number) {
    return index * 2 + 2;
  }

  //获取父节点元素位置
  getParentIndex(index: number) {
    if (index === 0) {
      return undefined;
    }
    return Math.floor((index - 1) / 2);
  }

  isEmpty() {
    return this.heap.length <= 0;
  }

  size() {
    return this.heap.length;
  }

  clear() {
    this.heap = [];
  }
}

这里是用的数组做存储,至于左右指针就以上面说的那样算

所以提供一个获取左右指针以及父指针的方法 + 以前经常用的方法

方法实现

insert方法

  // 插入值
  insert(value: T) {
    if (value != null) {
      //先插入到堆里去吧,这个是插入到最后,所以还要看这个数是否在这个位置
      this.heap.push(value);
      //上移操作
      this.siftUp(this.heap.length - 1);
      return true;
    }
    return false;
  }

这里是把值先push到数组中,添加到最尾部了,但是这个并不是说他就是在这个位置,所以需要进行数据上移操作

siftUp操作(递归版)

 siftUp(index: number) {
     //向上移动,所以与其父节点比较
     let pIndex = this.getParentIndex(index);
     //父级节点大于当前节点,那么就要交换位置
     if (index > 0 && this.compareFn(this.heap[pIndex], this.heap[index]) === Compare.BIGGER_THAN) {
      //将当前元素与父元素交换
      swap(this.heap, pIndex, index);
      //交换完成后我们要进行下一步比较,我们插入的元素在pIndex位置,但是我们不知道他是否到了该在的位置,所以继续
      this.siftUp(pIndex);
    }
  }

其实所谓的上移就是最简单的比较,我们现在弄最小堆,所以只要我们的新插入的值 < 父节点值,那就说明我们需要上移,那么就交换位置,注意:这里上移一个位置后,我们的目标就改到了父节点上,所以我们递归的index变成了pIndex

siftUp操作(迭代版)

 let parent = this.getParentIndex(index);
    while (
      index > 0 &&
      this.compareFn(this.heap[parent], this.heap[index]) === Compare.BIGGER_THAN
      ) {
      swap(this.heap, parent, index);
      index = parent;
      parent = this.getParentIndex(index);
}

注意事项同上

extract方法

移除最小值,基本思路就是

交换最后一个和第一个的位置

然后移除最后一个,并保存作为返回值

然后让第一个值向下找合适的位置(这里其实类似于上面的siftUp,区别不过是以前是一个数比较,现在子节点有两个,但是要找到最小的那个,一定要记得是最小的那个哦!!!)

为什么找最小的???[考虑第一次交换的情况,当前元素需要下移,并且在第一个节点上,需要找一个最小的放上面,作为根节点]

然后交换位置,然后继续下移,直到最后

extract() {
    //如果空,就不用移除了
    if (this.isEmpty()) {
      return undefined;
    }
    //如果有一个元素,就可以直接移除返回
    if (this.size() === 1) {
      return this.heap.shift();
    }
    //最后一个和第一个交换
    swap(this.heap, 0 , this.size() - 1)
    //弹出最后一个,并保留作为返回值
    let result = this.heap.pop();
    //开始向下移动
    this.siftDown(0);
    return result;
  }

siftDown操作

siftDown(index: number) {
    //获取左右的下标
    let leftIndex = this.getLeftIndex(index);
    let rightIndex = this.getRightIndex(index);

    // 定义index值 element
    let element = index;

    // 在有效范围内和左边元素比较,如果大就向下移动
    if(index < this.size() && this.compareFn(this.heap[element], this.heap[leftIndex]) === Compare.BIGGER_THAN){
      element = leftIndex;
    }
    //***  在有效范围内和右元素比较,如果大就向下移动   这里使用的是element,注意,因为element代表了最小的数
    if(index < this.size() && this.compareFn(this.heap[element], this.heap[rightIndex]) === Compare.BIGGER_THAN){
      element = rightIndex;
    }

    //确定位置结束
    if(element !== index){
      // 交换元素,下移当前元素
      swap(this.heap, index , element);
      // 然后递归,继续移动当前元素,但是这个时候就不再是index,而是element
      this.siftDown(element);
    }
  }

这里一定要注意的是***标注点处的使用element,因为index可能在左节点的时候被替换了,这里需要的是最小值

findMinimum方法

这个就不用多说了吧,就是取数组的第一个就好

//找最小的事
findMinimum() {
  return this.isEmpty() ? undefined : this.heap[0];
}

总结

到此堆的所有方法就实现了,整体来说堆的边界不是很复杂,所以还是比较简单的一种

其他

你说还没结束,哦,好像是的,忘记了两件事,一个最喜欢的贴代码,一个就是堆排序

function heapify(array: any[], index: number, heapSize: number, compareFn: Function) {
  let largest = index;
  const left = (2 * index) + 1;
  const right = (2 * index) + 2;

  if (left < heapSize && compareFn(array[left], array[index]) > 0) {
    largest = left;
  }

  if (right < heapSize && compareFn(array[right], array[largest]) > 0) {
    largest = right;
  }

  if (largest !== index) {
    swap(array, index, largest);
    heapify(array, largest, heapSize, compareFn);
  }
}

function buildMaxHeap(array: any[], compareFn: Function) {
  for (let i = Math.floor(array.length / 2); i >= 0; i -= 1) {
    heapify(array, i, array.length, compareFn);
  }
  return array;
}

export function heapSort(array: any[], compareFn = defaultCompareFn) {
  let heapSize = array.length;
  buildMaxHeap(array, compareFn);
  while (heapSize > 1) {
    swap(array, 0, --heapSize);
    heapify(array, 0, heapSize, compareFn);
  }
  return array;
}

方法就不多BB了,加油

所有代码

/*
*  二叉堆是二叉数,但是不一定是二叉搜索树
*
*  insert(value)
*  extract():移除最大堆的最大值或者最小堆的最小值
*  findMinimum():这个方法返回最小值(最小堆)或最大值(最大堆)且不会移除这个值
*
*  二叉堆以数组存数据   下标找节点
*  初始节点:         0
*           1              2
*       3      4        5      6
*    7    8  9   10  11  12 13  14
*                                        0
* 第二排(下标1):         0 * 2 + 1                      0 * 2 + 2
* 第三排(下标2): 1 * 2 + 1      1 * 2 + 2      2 * 2 + 1        2 * 2 + 2
*
*总结:
*左元素的位置: 当前下标 * 2 + 1
*右元素的位置: 当前下标 * 2 + 2
*/
enum Compare {
  LESS_THAN = -1,
  BIGGER_THAN = 1,
  EQUALS = 0
}

function defaultCompareFn<T>(parent: T, child: T) {
  if (parent === child) {
    return Compare.EQUALS
  }
  return parent > child ? Compare.BIGGER_THAN : Compare.LESS_THAN;
}
// 数组交换
function swap<T>(array: Array<T>, index: number, otherIndex: number) {
  [array[index], array[otherIndex]] = [array[otherIndex], array[index]];
}

export class MinHeap<T> {
  private heap: Array<T>;
  compareFn: Function;

  constructor(compareFn: Function = defaultCompareFn) {
    this.heap = [];
    this.compareFn = compareFn;
  }

  //获取左边子元素位置
  getLeftIndex(index: number) {
    return index * 2 + 1;
  }

  //获取右边子元素位置
  getRightIndex(index: number) {
    return index * 2 + 2;
  }

  //获取父节点元素位置
  getParentIndex(index: number) {
    if (index === 0) {
      return undefined;
    }
    return Math.floor((index - 1) / 2);
  }

  isEmpty() {
    return this.heap.length <= 0;
  }

  size() {
    return this.heap.length;
  }

  clear() {
    this.heap = [];
  }

  // 插入值
  insert(value: T) {
    if (value != null) {
      //先插入到堆里去吧,这个是插入到最后,所以还要看这个数是否在这个位置
      this.heap.push(value);
      this.siftUp(this.heap.length - 1);
      return true;
    }
    return false;
  }

  //以数组的形式返回数据
  getAsArray() {
    return this.heap
  }

  // 向上移动数据
  siftUp(index: number) {
    /*
     //向上移动,所以与其父节点比较
     let pIndex = this.getParentIndex(index);
     //父级节点大于当前节点,那么就要交换位置
     if (index > 0 && this.compareFn(this.heap[pIndex], this.heap[index]) === Compare.BIGGER_THAN) {
      //将当前元素与父元素交换
      swap(this.heap, pIndex, index);
      //交换完成后我们要进行下一步比较,我们插入的元素在pIndex位置,但是我们不知道他是否到了该在的位置,所以继续
      this.siftUp(pIndex);
    }
    */

    let parent = this.getParentIndex(index);
    while (
      index > 0 &&
      this.compareFn(this.heap[parent], this.heap[index]) === Compare.BIGGER_THAN
      ) {
      swap(this.heap, parent, index);
      index = parent;
      parent = this.getParentIndex(index);
    }
  }

  //找最小的事
  findMinimum() {
    return this.isEmpty() ? undefined : this.heap[0];
  }

  //移除堆中的最小值
  extract() {
    //如果空,就不用移除了
    if (this.isEmpty()) {
      return undefined;
    }
    //如果有一个元素,就可以直接移除返回
    if (this.size() === 1) {
      return this.heap.shift();
    }
    //最后一个和第一个交换
    swap(this.heap, 0 , this.size() - 1)
    //弹出最后一个,并保留作为返回值
    let result = this.heap.pop();
    //开始堆化
    this.siftDown(0);
    return result;
  }

  /**
   * 移动数据
   * 使第一个元素找到其正确的位置
   * 注意,此时的第一个元素是最大值(最小堆),所以这个时候只要向下找合适位置就可以了
   *
   * 这个方法其实和向上找(siftUp)是基本一样的,但是区别就在是有左右两个节点,所以我们基于前面说的原则,找到最小的那个即可
   */
  siftDown(index: number) {
    //获取左右的下标
    let leftIndex = this.getLeftIndex(index);
    let rightIndex = this.getRightIndex(index);

    // 定义index值 element
    let element = index;

    // 在有效范围内和左边元素比较,如果大就向下移动
    if(index < this.size() && this.compareFn(this.heap[element], this.heap[leftIndex]) === Compare.BIGGER_THAN){
      element = leftIndex;
    }
    // 在有效范围内和右元素比较,如果大就向下移动   这里使用的是element,注意,因为element代表了最小的数
    if(index < this.size() && this.compareFn(this.heap[element], this.heap[rightIndex]) === Compare.BIGGER_THAN){
      element = rightIndex;
    }

    //确定位置结束
    if(element !== index){
      // 交换元素,下移当前元素
      swap(this.heap, index , element);
      // 然后递归,继续移动当前元素,但是这个时候就不再是index,而是element
      this.siftDown(element);
    }
  }

  heapify(array: T[]) {
    if (array) {
      this.heap = array;
    }

    const maxIndex = Math.floor(this.size() / 2) - 1;

    for (let i = 0; i <= maxIndex; i++) {
      this.siftDown(i);
    }

    return this.heap;
  }
}

function defaultMaxCompareFn<T>(parent: T, child: T) {
  if (parent === child) {
    return Compare.EQUALS
  }
  return parent > child ? Compare.LESS_THAN : Compare.BIGGER_THAN
}

export class MaxHeap<T> extends MinHeap<T> {
  constructor(compareFn = defaultMaxCompareFn) {
    super(compareFn);
  }
}

function heapify(array: any[], index: number, heapSize: number, compareFn: Function) {
  let largest = index;
  const left = (2 * index) + 1;
  const right = (2 * index) + 2;

  if (left < heapSize && compareFn(array[left], array[index]) > 0) {
    largest = left;
  }

  if (right < heapSize && compareFn(array[right], array[largest]) > 0) {
    largest = right;
  }

  if (largest !== index) {
    swap(array, index, largest);
    heapify(array, largest, heapSize, compareFn);
  }
}

function buildMaxHeap(array: any[], compareFn: Function) {
  for (let i = Math.floor(array.length / 2); i >= 0; i -= 1) {
    heapify(array, i, array.length, compareFn);
  }
  return array;
}

export function heapSort(array: any[], compareFn = defaultCompareFn) {
  let heapSize = array.length;
  buildMaxHeap(array, compareFn);
  while (heapSize > 1) {
    swap(array, 0, --heapSize);
    heapify(array, 0, heapSize, compareFn);
  }
  return array;
}

书本代码

enum Compare {
  LESS_THAN = -1,
  BIGGER_THAN = 1,
  EQUALS = 0
}

function defaultCompare<T>(a: T, b: T): number {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

type ICompareFunction<T> = (a: T, b: T) => number;

function reverseCompare<T>(compareFn: ICompareFunction<T>): ICompareFunction<T> {
  return (a, b) => compareFn(b, a);
}

function swap(array: any[], a: number, b: number) {
  /* const temp = array[a];
  array[a] = array[b];
  array[b] = temp; */
  [array[a], array[b]] = [array[b], array[a]];
}

export class MinHeap<T> {
  protected heap: T[] = [];

  constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {}

  private getLeftIndex(index: number) {
    return 2 * index + 1;
  }

  private getRightIndex(index: number) {
    return 2 * index + 2;
  }

  private getParentIndex(index: number) {
    if (index === 0) {
      return undefined;
    }
    return Math.floor((index - 1) / 2);
  }

  size() {
    return this.heap.length;
  }

  isEmpty() {
    return this.size() <= 0;
  }

  clear() {
    this.heap = [];
  }

  findMinimum() {
    return this.isEmpty() ? undefined : this.heap[0];
  }

  insert(value: T) {
    if (value != null) {
      const index = this.heap.length;
      this.heap.push(value);
      this.siftUp(index);
      return true;
    }
    return false;
  }

  private siftDown(index: number) {
    let element = index;
    const left = this.getLeftIndex(index);
    const right = this.getRightIndex(index);
    const size = this.size();

    if (left < size && this.compareFn(this.heap[element], this.heap[left]) === Compare.BIGGER_THAN) {
      element = left;
    }

    if (
      right < size &&
      this.compareFn(this.heap[element], this.heap[right]) === Compare.BIGGER_THAN
    ) {
      element = right;
    }

    if (index !== element) {
      swap(this.heap, index, element);
      this.siftDown(element);
    }
  }

  private siftUp(index: number): void {
    let parent = this.getParentIndex(index);
    while (
      index > 0 &&
      this.compareFn(this.heap[parent], this.heap[index]) === Compare.BIGGER_THAN
    ) {
      swap(this.heap, parent, index);
      index = parent;
      parent = this.getParentIndex(index);
    }
  }

  extract() {
    if (this.isEmpty()) {
      return undefined;
    }
    if (this.size() === 1) {
      return this.heap.shift();
    }
    const removedValue = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.siftDown(0);
    return removedValue;
  }

  heapify(array: T[]) {
    if (array) {
      this.heap = array;
    }

    const maxIndex = Math.floor(this.size() / 2) - 1;

    for (let i = 0; i <= maxIndex; i++) {
      this.siftDown(i);
    }

    return this.heap;
  }

  getAsArray() {
    return this.heap;
  }
}

export class MaxHeap<T> extends MinHeap<T> {
  constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {
    super(compareFn);
    this.compareFn = reverseCompare(compareFn);
  }
}

表示这一周本来是说两个章节的,可是工作还有生活原因(这都是假的,主要是自己蠢,后面的图,迷迷糊糊的,唉!!!)

然后发现自己胖了,胖得不行了,所以下周开始减肥,并且满满的日程,但是学习不能断呀!!!还是会尽量基础时间学习,毕竟现在太弱鸡了,唉着急!!!!
下周排序,有兴趣的可以留意我一下哦!!!

第十一章 二叉堆

简介

结构

创建我们的最小堆

选择存储数据的数据类型

基础方法

基础方法

基础结构

方法实现

insert方法

siftUp操作(递归版)

siftUp操作(迭代版)

extract方法

siftDown操作

findMinimum方法

总结

其他

所有代码

书本代码

相关推荐

第十一章二叉堆