数据结构-堆

经过一轮轮的秋招面试，体会到数据结构的重要性，打算系统的学习一遍

api 设计

实现堆

class Heap {
    constructor(){
        // 储存堆中的元素
        this.items = []
        // 记录堆中元素的个数
        this.n = 0
    }

    // 判断堆中索引 i 处的元素是否小于索引 j 处的元素
    less( i=0, j=0 ){
        return this.items[i] < this.items[j]
    }
    // 交换堆中索引 i 和 j 处的值
    swop( i=0, j=0 ){
        [ this.items[i], this.items[j] ] = [ this.items[j], this.items[i] ]
    }
    // 删除堆中最大的元素，并返回这个最大的元素
    deleteMax(){
        let max = this.items[ 1 ]
        // 交换索引 1 处的元素与最大索引处的元素，让完全二叉树的最右侧元素变为根节点
        this.swop( 1, this.n )
        // 删除最大元素
        this.items[ this.n ] = null
        // 元素个数 -1
        this.n --
        // 通过下沉调整堆，让堆重新有序
        this.sink( 1 )
        return max
    }

    // 往堆中插入一个元素
    insert( value ){
        this.items[ ++this.n ] = value
        this.swim( this.n )
    }

    // 使用上浮算法，使索引 k 处的元素能在堆中处于正确的位置
    swim( k=0 ){
        // 父级链进行比较
        while( k > 1 ){
            // 比较当前节点和其父节点
            if( this.less( Math.floor( k/2 ), k ) ){
                this.swop( Math.floor( k/2 ), k )
            }
            k = Math.floor( k/2 )
        }
    }

    // 使用下沉算法，使索引 k 处的元素能在堆中处于正确的位置
    sink( k=0 ){
        // 通过循环不断对比当前 k 节点和其左子节点 2*k 以及 右子节点 2*k+1 处中较大值的元素
        while( 2*k <= this.n ){
            // 获取当前节点的子节点中较大的节点
            let max  // 记录较大节点所在的索引
            if( 2*k + 1 <= this.n ){
                if( this.less( 2*k, 2*k + 1 ) ){
                    max = 2*k + 1
                } else {
                    max = 2*k
                }
            } else {
                max = 2*k
            }
            // 比较当前节点和较大节点的值
            if( this.less( max, k ) ){
                break
            }
            // 交换 k 索引处的值和 max 做阴处的值
            this.swop( k, max )

            // 变换 k 的值
            k = max
        }
    }
}

// 测试
let myHeap = new Heap()
myHeap.insert(1)
myHeap.insert(2)
myHeap.insert(3)
myHeap.insert(4)
myHeap.insert(5)
myHeap.insert(6)

let res = null
while( (res = myHeap.deleteMax()) !== null ){
    console.log( res )
}

实现堆排序的堆

 // 堆排序
class HeapSort {
    // 判断 heap 堆中索引 i 处的元素是否小于索引 j 处的元素
    less( heap=[], i=0, j=0 ){
        return heap[i] < heap[j]
    }
    // 交换 heap 堆中 i 索引和 j 索引的值
    swop( heap=[], i=0, j=0 ){
        [ heap[i], heap[j] ] = [ heap[j], heap[i] ]
    }
    // 根据原数据 source，构造出堆 heap
    createHeap( source=[], heap=[] ){
        // 把 source 中的元素拷贝到 heap 中，heap 是一个无序堆
        // 将第一个元素空出来
        heap.push( "", ...source )
        // 对堆中的元素做下沉调整（从长度的一半开始下沉）
        for( let i = Math.floor( source.length / 2 ); i > 0; i -- ){
            this.sink( heap, i, heap.length-1 )
        }
    }

    sink( heap=[], target=0, range=0 ){
        while( 2*target <= range ){
            // 找出当前节点较大的子节点
            let max
            if( 2*target+1 <= range ){
                if( this.less( heap, 2*target, 2*target+1 ) ){
                    max = 2*target+1
                } else {
                    max = 2*target
                }
            } else {
                max = 2*target
            }
            // 比较当前节点的值和较大节点的值
            if( !this.less( heap, target, max ) ){
                break
            }
            this.swop( heap, target, max )
            target = max
        }
    }
    sort( source=[] ){
        // 构建堆
        let newHeap = []
        this.createHeap( source, newHeap )
        console.log( "变换后的堆：", newHeap )
        // 定义一个变量，记录为排序的元素中最大的索引
        let n = newHeap.length - 1
        // 通过循环，交换1索引处的元素和排序的元素中最大的索引的元素
        while( n > 1 ){
            // 交换元素
            this.swop( newHeap, 1, n )
            // 排除交换后最大元素所在的索引，让他不要参与下沉
            n --
            // 对索引1处的元素进行下沉调整
            this.sink( newHeap, 1, n )
        }
        // 把 heap 中的数据复制到原 source 中
        console.log( "交换后的堆：", newHeap )
        newHeap.shift()
        source.length = 0
        source.push( ...newHeap )
    }
}


// 测试
// 待排序的数组
let sourceArr = [ "S","O","R","T","E","X","A","M","P","L","E" ]
// 通过 heapSort 对数组进行排序
let heapSort = new HeapSort()
heapSort.sort( sourceArr )

console.log( sourceArr )