class MinHeap {
    constructor() {
        this.heap = []
    }

    //使用普通数组实现的二叉树节点

    //1.左侧子节点的位置是2*index+1
    //右侧子节点是2*index+2
    //父节点的位置是(index - 1) / 2

    //获取左侧子节点
    getLeftIndex(index) {
        return 2 * index + 1
    }

    //获取右侧子节点
    getRightIndex(index) {
        return 2 * index + 2
    }

    //获取父节点
    getParentIndex(index) {
        return index === 0 ? undefined : Math.floor((index - 1) / 2)
    }
    //上移操作
    siftUp(index) {
        let parent = this.getParentIndex(index)
        while (index > 0 && this.heap[parent] > this.heap[index]) {
            [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]]
            index = parent
            parent = this.getParentIndex(index)

        }
    }

    siftDown(index) {
        // 移除最小值（最小堆）或最大值（最大堆）
        // 表示移除数组中的第一个元素（堆的根节点）。
        // 在移除后，我们将堆的最后一个元素移动至根部并执行siftDown函数，
        // 表示我们将交换元素直到堆的结构正常
        //[0,1,2,3,4,5,6,7]
        //[2,3,4,5,6,7,8,9]
        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) {
            [this.heap[index], this.heap[element]] = [this.heap[element], this.heap[index]]
            this.siftDown(element)

        }


    }
    //向堆中插入新的值
    insert(value) {
        if (value !== null) {
            this.heap.push(value)//将值插入到堆的底部叶节点
            this.siftUp(this.heap.length - 1) //将这个值和他的父节点进行交换

            return true
        }
        return false
    }
    //移除最小值或最大值并返回这个值
    extract() {
        if (this.isEmpty()) {
            return undefined
        }

        if (this.size() === 1) {
            return this.heap.shift()
        }

        const removedValue = this.heap[0]
        console.log('removedValue', removedValue);
        this.heap[0] = this.heap.pop()
        this.siftDown(0)

        return removedValue


    }
    // 返回最小值或最大值且不会移除
    findMinimun() {
        return this.isEmpty() ? undefined : this.heap[0]
    }

    size() {
        return this.heap.length
    }

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

const arr = [5, 23, 6, 0, 66, 77, 33, 46, 4, 3, 2, 1]

function heapSort(arr) {
    const heap = new MinHeap()
    //构建最小堆
    for (const e of arr) {
        heap.insert(e)
    }
    const result = []
    console.log('heap.length', heap.size());

    while (heap.size() > 0) {
        result.push(heap.extract())
    }

    return result
}

console.log(heapSort(arr));