阅读 76

堆(最大堆)和堆排序---typescript实现

一. 定义

  1. 堆(Heap)是一个可以被看成近似完全二叉树的数组。树上的每一个结点对应数组的一个元素。所谓完全二叉树,即为除了最底层外,该树是完全充满的,而且是从左到右填充。-----《算法导论》
  2. 最大堆,即为堆中某个节点(除去根节点)的值总是不大于其父节点的堆
  3. 最小堆,即为堆中某个节点(除去根节点)的值总是不小于其父节点的堆。

二. 优势

对于实现优先队列,堆这种数据结构可以在入队和出队时,时间复杂度都稳定在O(lgn)级别

三. 实现

我们用数组存储二叉堆,索引从1开始,对于一个节点,索引为i,其左孩子节点left索引为 2 * i, 右孩子节点right索引为2 * i + 1, 父亲节点parent索引为Math.floor(i / 2)

堆常见的操作:

  1. heapify: 将一个无序数组建立成堆的过程,时间复杂度O(n)
  2. insert: 将一个元素插入到堆中,并保持堆的结构,时间复杂度O(lgn)
  3. extractMax(extractMin): 取出堆中最大(对于最小堆则是最小)的元素,并保持剩余元素依旧维持堆结构,时间复杂度O(lgn)
  4. heapsort: 使用堆对数组进行排序,时间复杂度O(nlgn)
  5. shiftUpshiftDown操作的图示:

下面给出最大堆的typescript实现,配有详细的注释

class MaxHeap<T> {
    // 实现堆的数组(T代表用户可以存储任意数据类型)
    private maxHeap: T []
    // 堆中数据量
    private size: number = 0
    // 堆容量
    // 根据用户指定的容量初始化一个数组,实际上js数组是动态的,是不需要指定定数组长度的,可以不需要指定容量
    // 这里我们限制为一个有容量限制的堆,你可以不加这个限制
    private capacity!: number
    // 构造堆时候,支持传入容量或者容量和一个初始化数组
    constructor (capacity: number)
    constructor (capacity: number, arr: T [])
    
    constructor (capacity: number, arr?: T []) {
        // 我们从索引1位置开始实现
        this.capacity = capacity
        this.maxHeap = new Array(capacity + 1)
        // heapify过程
        if (arr) {
            for (let i = 0; i < capacity; i++) {
                this.maxHeap[i + 1] = arr[i]
            }
            this.size = capacity
            for (let i = Math.floor(this.size / 2); i >= 1; i--) {
                this.shiftDown(i)
            }
        }
    }
    
    // 返回堆中有多少个元素
    public getSize (): number {
        return this.size
    }
    // 堆是否为空
    public isEmpty (): boolean {
        return this.size === 0
    }
    // 向最大堆中添加元素 shift up
    // 首先,元素放置在堆末尾,然后依次比较其和其父节点大小,比父节点大,则和父节点交换位置,直到不大于父节点值为止
    public insert (item: T): void {
        // 我们从索引1位置开始实现
        if (this.size + 1 <= this.capacity) {         
            this.maxHeap[this.size + 1] = item
            this.size ++
            this.shiftUp(this.size)
        }
    }

    // 从堆中取出一个元素(只能取出根节点的元素,这也是实现优先队列的核心) shiftDown
    // 首先,取出堆的根节点,之后把堆的最后一个元素放到根节点位置,然后依次比较其和其左右子节点大小,比子节点小,则和子节点中较大的交换位置,
    // 持续这个过程,直到再次满足最大堆定义
    public extractMax (): T {
        if (this.size > 0) {
            const item = this.maxHeap[1]
            // 交换堆顶和堆尾元素
            this.swap(1, this.size)
            // 没有必要删除,size--后,不会访问到了
            this.size --
            this.shiftDown(1)
            return item
        }
    }

    // 实现元素从index位置向上移动到正确位置的过程
    private shiftUp (index: number): void {
        // 对于一个节点,索引为i,其父亲节点parent: Math.floor(i / 2)
        // 注意,这里比较大小的方法,可能会根据堆中存储元素类型的不同,做改变,这里只是个示意
        while (index > 1 && this.maxHeap[Math.floor(index / 2)] < this.maxHeap[index]) {
            this.swap(Math.floor(index / 2), index)
            index = Math.floor(index / 2)
        }
    }

    // 实现元素从index位置向下移到正确位置的过程
    private shiftDown (index: number): void {
        while (2 * index <= this.size) {
            let i = 2 * index
            // 注意,这里比较大小的方法,可能会根据堆中存储元素类型的不同,做改变,这里只是个示意
            if (i + 1 <= this.size && this.maxHeap[i + 1] > this.maxHeap[i]) {
                i += 1
            }
            // 已经移到了正确位置
            if (this.maxHeap[index] >= this.maxHeap[i]) {
                break
            }
            this.swap(index, i)
            index = i
        }
    }

    // 交换数组两个索引位置的元素
    private swap (i: number, j: number): void {
        const temp = this.maxHeap[i]
        this.maxHeap[i] = this.maxHeap[j]
        this.maxHeap[j] = temp
    }
}
复制代码

四. 堆排序

给出堆排序的三种方法:排序arr数组中前n个元素,从小到大

// 堆排序第一种实现
function heapSort1<T>(arr: T [], n: number): void {
    const maxHeap: MaxHeap<T> = new MaxHeap<T>(n)
    // 数据入堆(O(nlog(n))
    for (let i = 0; i < n; i++) {
        maxHeap.insert(arr[i])
    }
    // 从小到大排序(O(nlog(n))
    for (let i = n - 1; i >= 0; i--) {
        arr[i] = maxHeap.extractMax()
    }
}
// 堆排序第二种实现(使用heapify过程)
// 复杂度(O(n))
function heapSort2<T>(arr: T [], n: number): void {
    const maxHeap: MaxHeap<T> = new MaxHeap<T>(n, arr)
    // 从小到大排序
    for (let i = n - 1; i >= 0; i--) {
        arr[i] = maxHeap.extractMax()
    }
}

// 堆排序第三种实现(原地排序)----这里数组索引从0开始
function heapSort3<T>(arr: T [], n: number): void {
    // 数组的索引从0开始
    for (let i = Math.floor((n - 1 - 1) / 2); i >= 0; i--) {
        shiftDown(arr, i, n)
    }
    // 从小到大排序
    for (let i = n - 1; i > 0; i--) {
        shiftDown(arr, 0, i)
    }
}

// 类似堆中的shiftDown
function shiftDown<T>(arr: T [], index: number, n: number): void {
    // 数组索引从0开始,所以判断条件微调
    while (2 * index + 1 < n) {
        let i = 2 * index + 1
        // 注意,这里比较大小的方法,可能会根据堆中存储元素类型的不同,做改变,这里只是个示意
        if (i + 1 < n && arr[i + 1] > arr[i]) {
            i += 1
        }
        // 已经移到了正确位置
        if (arr[index] >= arr[i]) {
            break
        }
        this.swap(index, i)
        index = i
    }
}
复制代码