1.0 問(wèn)題描述

實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)：堆炼绘。

2.0 問(wèn)題分析

1. 堆一般使用數(shù)組來(lái)表示脓魏，其中某個(gè)節(jié)點(diǎn)下標(biāo)i的兩個(gè)子節(jié)點(diǎn)的下標(biāo)為 2i+1 和 2i+2乘瓤。堆是一棵完全二叉樹(shù)晌砾。
2. 堆有3種基本操作：創(chuàng)建，插入规肴，刪除鲁冯。
3. 這3種操作都需要通過(guò)“調(diào)整堆”的方式來(lái)實(shí)現(xiàn)垃帅。調(diào)整堆是指缨叫，對(duì)堆中的某個(gè)節(jié)點(diǎn)椭符，若它的值和它所有子節(jié)點(diǎn)相比，不是最大/最小耻姥，那么就需要將最大/最小的元素和當(dāng)前節(jié)點(diǎn)交換销钝，這種操作成為“調(diào)整堆”。
4. 創(chuàng)建可以用插入來(lái)實(shí)現(xiàn)（復(fù)雜度O(nlogn)）琐簇，也可以使用數(shù)組直接轉(zhuǎn)換成堆（復(fù)雜度O(n)）蒸健。
5. 假設(shè)數(shù)組長(zhǎng)度為n，那么這個(gè)數(shù)組轉(zhuǎn)成堆婉商，需要從第一個(gè)有子節(jié)點(diǎn)的節(jié)點(diǎn)((n - 1)/2或(n - 2)/2開(kāi)始似忧，倒序“調(diào)整堆”，直到下標(biāo)為0据某。
6. 插入操作可以先將數(shù)據(jù)插入到數(shù)組尾部橡娄，然后依次調(diào)整該數(shù)據(jù)的父節(jié)點(diǎn)诗箍，父節(jié)點(diǎn)的父節(jié)點(diǎn)......直到根節(jié)點(diǎn)癣籽。
7. 刪除操作可以先將數(shù)組首尾節(jié)點(diǎn)互換挽唉，然后刪除最后面的元素，最后再調(diào)整根節(jié)點(diǎn)即可筷狼。

3.0 代碼實(shí)現(xiàn)

3.1使用swift實(shí)現(xiàn)

/*
 * 堆類型
 * small 小根堆
 * big 大根堆
 */
enum HeapType {
    case small, big
}

/*
 * 堆
 */
class Heap<T: Comparable> {
    private var _arr: [T];
    private var _type: HeapType;
    
    /*
     * 使用數(shù)組創(chuàng)建堆
     * @param {[T]} - arr 創(chuàng)建堆的數(shù)組
     * @param {HeapType} - type 堆類型
     */
    init(arr: [T], type: HeapType = .big) {
        self._arr = arr;
        self._type = type;
        self._create();
    }
    
    /*
     * 調(diào)整堆：調(diào)整以idx為頂?shù)?元素子堆瓶籽，若頂部元素不是最大/最小，則調(diào)整為最大/最小
     * @param {Int} - idx 表示調(diào)整以idx為頂?shù)?元素子堆
     * @return {Bool} - 調(diào)整成功返回true埂材，無(wú)需調(diào)整返回false
     */
    @discardableResult
    private func _adjust(_ idx: Int) -> Bool{
        let maxAdjustIdx = Int(ceilf(Float(_arr.count) / 2) - 1);
        if idx > maxAdjustIdx || idx < 0{
            return false;
        }
        let leftIdx = 2 * idx + 1;
        let rightIdx = 2 * idx + 2;
        let top: T? = _arr[idx];
        let left: T? = leftIdx < _arr.count ? _arr[leftIdx]: nil;
        let right: T? = rightIdx < _arr.count ? _arr[rightIdx]: nil;
        if let t = top {
            if let l = left, let r = right {
                let v = self._type == .big ? max(t, l, r) : min(t, l, r);
                switch v {
                case l:
                    swapArr(arr: &_arr, f: leftIdx, t: idx);
                    _adjust(leftIdx);
                    return true;
                case r:
                    swapArr(arr: &_arr, f: rightIdx, t: idx);
                    _adjust(rightIdx);
                    return true;
                default:
                    break;
                }
            }else if let l = left {
                let b = self._type == .big ? (l > t) : (l < t);
                if b {
                    swapArr(arr: &_arr, f: leftIdx, t: idx);
                    _adjust(leftIdx);
                    return true;
                }
            }else if let r = right {
                let b = self._type == .big ? (r > t) : (r < t);
                if b {
                    swapArr(arr: &_arr, f: rightIdx, t: idx);
                    _adjust(rightIdx);
                    return true;
                }
            }
        }
        return false;
    }
    
    /**
     * 創(chuàng)建堆塑顺，依次調(diào)整 n/2 -> 0 元素
     */
    private func _create(){
        let maxAdjustIdx = Int(ceilf(Float(_arr.count) / 2) - 1);
        for i in stride(from: maxAdjustIdx, to: -1, by: -1){
            _adjust(i);
        }
    }
    
    /**
     * 彈出一個(gè)元素，移除頂部元素俏险，然后令頂部元素等于最后一個(gè)元素严拒，最后調(diào)整頂部元素
     * @return [T?] 返回頂部元素
     */
    func pop() -> T? {
        let first = _arr.first;
        if first != nil {
            if _arr.count <= 1 {
                _arr.removeLast();
            }else{
                swapArr(arr: &_arr, f: 0, t: _arr.count - 1);
                _arr.removeLast();
                _adjust(0);
            }
        }
        return first;
    }
    
    /**
     * 插入一個(gè)元素，插入到尾部竖独，依次調(diào)整該元素的頂部元素裤唠，直到無(wú)需調(diào)整或下標(biāo)為0
     * @param {T} - t 插入的元素
     */
    func push(_ t: T){
        _arr.append(t);
        var idx = Int(ceilf(Float(_arr.count - 1) / 2) - 1);
        while true {
            if !_adjust(idx){
                break;
            }
            if idx == 0{
                break;
            }
            idx = Int(ceilf(Float(idx) / 2) - 1);
        }
    }
    
    /**
     * 返回當(dāng)前元素?cái)?shù)量
     * @return {Int} 返回堆內(nèi)元素?cái)?shù)量
     */
    func count() -> Int{
        return _arr.count;
    }
}

3.2使用js實(shí)現(xiàn)

//常量
const BigHeap = 1;
const SmallHeap = 2;

//構(gòu)造函數(shù)
function Heap(type, arr, compareFunction){
    this.type = type;
    this.arr = arr;
    this.compareFunction = compareFunction;
    this._createHeap(arr);
}

//數(shù)組交換
Heap._swap = function(i,j,arr){
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

//比較值
Heap.prototype._compare = function(v1, v2){
    if(this.type == SmallHeap){
        if(v2 == null){
            return true;
        }else{
            if(this.compareFunction){
                return this.compareFunction(v1, v2) == -1;
            }else{
                return v1 < v2;
            }
        }
    }else{
        if(v2 == null){
            return true;
        }else{
            if(this.compareFunction){
                return this.compareFunction(v1, v2) == 1;
            }else{
                return v1 > v2;
            }
        }
    }
}

//調(diào)整堆的第i個(gè)結(jié)點(diǎn)
Heap.prototype._adjustNode = function(i, arr){
    let leftChildIdx = 2 * i + 1;
    let leftValue = null;
    if(leftChildIdx < arr.length){
        leftValue = arr[leftChildIdx];
    }
    let rightChildIdx = 2 * i + 2;
    let rightValue = null;
    if(rightChildIdx < arr.length){
        rightValue = arr[rightChildIdx];
    }
    if(!leftValue && !rightValue){
        return;
    }
    let exchangeIdx = null;
    //左值存在并且大于根結(jié)點(diǎn)
    if(leftValue && this._compare(leftValue, arr[i])){
        //右值存在并且大于左結(jié)點(diǎn)
        if(rightValue && this._compare(rightValue, leftValue)){
            //右值交換
            exchangeIdx = rightChildIdx;
        }else{
            //左值交換
            exchangeIdx = leftChildIdx;
        }
    }else if(rightValue && this._compare(rightValue, leftValue)){
        //右值交換
        exchangeIdx = rightChildIdx;
    }

    if(exchangeIdx != null){
        Heap._swap(exchangeIdx, i, arr);
        //交換完畢后，新的子結(jié)點(diǎn)也需要調(diào)整
        this._adjustNode(exchangeIdx, arr);
    }
}

//根據(jù)數(shù)組創(chuàng)建堆
Heap.prototype._createHeap = function(arr){
    let len = arr.length;
    if(len <= 1){
        return;
    }
    //最后一個(gè)非葉子結(jié)點(diǎn)
    let lastNonLeafIdx = Math.floor(len / 2) - 1;
    //依次調(diào)整每個(gè)結(jié)點(diǎn)
    for (let index = lastNonLeafIdx; index >= 0; index--) {
        this._adjustNode(index, arr);
    }
}

//插入
Heap.prototype.insert = function(ele){
    this.arr.push(ele);
    let adjustIdx = this.arr.length;
    while(adjustIdx > 0){
        adjustIdx = Math.ceil(adjustIdx / 2) - 1;
        this._adjustNode(adjustIdx, this.arr);
        if(adjustIdx <= 0){
            break;
        }
    }
}

//刪除
Heap.prototype.remove = function(){
    if(this.arr.length <= 0){
        return null;
    }
    let value = this.arr[0];
    if(this.arr.length > 1){
        this.arr[0] = this.arr.pop();
        this._adjustNode(0, this.arr);
    }else{
        this.arr.pop();
    }
    return value;
}

//是否為空
Heap.prototype.empty = function(){
    return this.arr.length == 0 || this.arr[0] == null;
}

4.0 復(fù)雜度分析

1. 數(shù)組轉(zhuǎn)堆的復(fù)雜度
   • 首先需要進(jìn)行n/2次堆的調(diào)整
   • 每次調(diào)整堆最多可能需要 logn次的二次調(diào)整
     • 所以時(shí)間復(fù)雜度小于 O(nlogn)
   • 每次調(diào)整堆最少可能需要1次調(diào)整
     • 所以時(shí)間復(fù)雜度大于O(n/2)
   • 實(shí)際上莹痢，需要少量調(diào)整的操作數(shù)遠(yuǎn)遠(yuǎn)大于需要多次調(diào)整的操作种蘸。
     • 根據(jù)調(diào)整規(guī)則，設(shè)最高高度為h = logn
     • 根節(jié)點(diǎn)需要調(diào)整次數(shù)為：2^0*h
     • 第二層需要調(diào)整次數(shù)為：2^1*(h-1)
     • ... ...
     • 第logn層需要調(diào)整次數(shù)為：2^(h-1)*1
     • 總次數(shù)count=2^0*h + 2^1*(h-1) + 2^2*(h-2) + ... + 2^(h-1)*(h-(h-1)) //使用錯(cuò)位相減
     • count*2 = 2^1*h + 2^2*(h-1) + 2^3*(h-2) + ... + 2^h*(h-(h-1))
     • count = count*2-count = 2^1 + 2^2 + ... + 2^(h-1) + 2^h - 2^0*h
     • count = 2^(h+1) - 2 - h
     • count = 2n - 2 - logn
     • 所以時(shí)間復(fù)雜度為O(n)
2. 堆的插入：O(logn)
3. 堆的刪除：O(logn)