11-chapter_堆

[wl05]

堆的实现

function swap(array, a, b) {
    [array[a], array[b]] = [array[b], array[a]]
}

class MinHeap {
    heap = []
    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)
    }

    size() {
        return this.heap.length
    }

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

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

    /**
     * 堆化操作
     * @param index
     */
    siftDown(index) {
        let element = index
        const left = this.getLeftIndex(index)
        const right = this.getRightIndex(index)
        const size = this.size()
        if (left < size && this.heap[element] > this.heap[left]) {
            element = left
        }
        if (right < size && this.heap[element] > this.heap[right]) {
            element = right
        }
        if (index !== element) {
            swap(this.heap, index, element)
            this.siftDown(element)
        }
    }

    siftUp(index) {
        let parent = this.getParentIndex(index)
        while (index > 0 && this.heap[parent] > this.heap[index]) {
            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) {
        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 swap(array, a, b) {
    [array[a], array[b]] = [array[b], array[a]]
}

function heapify(array, index, heapSize) {
    let largest = index
    const left = (2 * index) + 1
    const right = (2 * index) + 2
    if (left < heapSize && array[left] - array[index] > 0) {
        largest = left
    }
    if (right < heapSize && array[right] - array[largest] > 0) {
        largest = right
    }
    if (largest !== index) {
        swap(array, index, largest)
        heapify(array, largest, heapSize)
    }
}

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

function heapSort(array) {
    let heapSize = array.length
    buildMaxHeap(array)
    while (heapSize > 1) {
        swap(array, 0, --heapSize)
        heapify(array, 0, heapSize)
    }
    return array
}


const array = [7, 6, 3, 5, 4, 1, 2]
console.log('Before sorting: ', array)
console.log('After sorting: ', heapSort(array))

参考资料

1. 数据结构------堆(二、堆的实现)