二叉堆和堆排序
- 二叉堆数据结构
  - 创建最小堆类
  - 堆排序算法

二叉堆和堆排序

二叉堆数据结构

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

它是一颗完全二叉树，表示树的每一层都有左侧和右侧子节点（除了最后一层的叶节点），并且最后一层的叶节点尽可能都是左侧子节点，这叫作结构特性。
二叉堆不是最小堆就是最大堆。最小堆允许你快速导出树的最小值，最大堆允许你快速导出树的最大值。所有的节点都大于等于（最大堆）或小于等于（最小堆）每个它的子节点。这叫作堆特性。

尽管二叉堆是二叉树，但并不一定是二叉搜索树。在二叉堆里，每个子节点都要大于等于父节点（最小堆）或小于等于父节点（最大堆）。

创建最小堆类

import { defaultCompare } from './util';
export class MinHeap {
    constructor(compareFn = defaultCompare) {
        this.compareFn = compareFn;
        this.heap = [];
    }
}

1.二叉树的数组表示。

二叉树有两种表示方式。第一种是使用一个动态的表示方式，也就是指针。第二种是使用一个数组，通过索引值检索父节点、左侧和右侧子节点的值。

要访问使用普通数组的二叉树节点，可以用下面的方式操作index。

对于给定位置index的节点：

它的左侧子节点的位置是2*index+1；

它的右侧子节点的位置是2*index+2；

它的父节点位置是index/2。

用上面的方法访问特定节点，我们可以把下面的方法加入MinHeap类。

getLeftIndex(index) {
    return 2 * index + 1;
}
getRightIndex(index) {
    return 2 * index + 2;
}
getParentIndex(index) {
    if(index === 0) {
        return undefined;
    }
    return Math.floor((index - 1) / 2);
}

我们可以在堆数据结构中进行三个主要操作。

insert(value)：向堆中插入一个新的值。成功返回true，否则返回false。

extract()：移除最小值（最小堆）或最大值（最大堆）并返回这个值。

findMinimum()：返回最小值或最大值且不会移除这个值。

    //向堆中插入值
    //指将值插入堆的底部叶节点再执行siftUp方法，表示要将这个值和它的父节点进行交换
    //直到父节点小于这个插入的值。
    insert(value) {
        if(value != null) {
            this.heap.push(value);
            this.siftUp(this.heap.length - 1);
            return true;
        }
        return false;
    }
    //上移操作
    siftUp(index) {
        let parent = this.getParentIndex(index);
        while(index > 0 && this.compareFn(this.heap[parent], this.heap[index]) > this.compareFn.BIGGER_THAN) {
            swap(this.heap, parent, index);
            index = parent;
            parent = this.getParentIndex(index);
        }
    }
    //从堆中找到最小值或最大值
    //在最小堆中，最小值总是位于数组的第一个位置
    size() {
        return this.heap.length;
    }
    isEmpty() {
        return this.size() === 0;
    }
    findMinimum() {
        return this.isEmpty() ? undefined : this.heap[0];
    }
    // 导出堆中的最小值或最大值
    // 移除最小值或最大值表示移除数组中的第一个元素。在移除后，我们将堆的最后一个元素移动至根部并执行siftDown函数
    // 表示我们将交换元素直到堆的结构正常。
    extract() {
        if(this.isEmpty()) {
            return undefined;
        }
        if(this.size() === 1) {
            return this.heap.shift();
        }
        const removedValue = this.heap.shift();
        this.heap[0] = this.heap.pop()
        this.siftDown(0);
        return removedValue
    }
    siftDown(index) {
        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);
        }
    }
function swap(array, a, b ) {
        const temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

堆排序算法

用数组创建一个最大堆用作数据源。
在创建最大堆后，最大的值会被存储在堆的第一个位置。我们要将它替换为堆的最后一个值，将堆的大小减1.
最后我们将堆的根节点下移并重复步骤2直到堆的大小为1。

我们用最大堆得到一个升序排列的数组，如果想要数组降序排列，可以用最小堆代替。

function heapSort(array, compareFn = defaultCompare) {
    let heapSize = array.length;
    buildMaxHeap(array, compareFn);
    while(heapSize > 1) {
        swap(array, 0, --heapSize);
        heapify(array, 0, heapSize, compareFn);
    }
    return array;
}
function buildMaxHeap(array, compareFn) {
    for(let i = Math.floor(array.length / 2); i >= 0; i -= 1) {
        heapify(array, i, array.length, compareFn);
    }
    return array;
}