阅读 2

算法(4)数据结构:堆

1.0 问题描述

实现数据结构:堆。

2.0 问题分析

  1. 堆一般使用数组来表示,其中某个节点下标i的两个子节点的下标为 2i+1 和 2i+2。堆是一棵完全二叉树。
  2. 堆有3种基本操作:创建,插入,删除。
  3. 这3种操作都需要通过“调整堆”的方式来实现。调整堆是指,对堆中的某个节点,若它的值和它所有子节点相比,不是最大/最小,那么就需要将最大/最小的元素和当前节点交换,这种操作成为“调整堆”。
  4. 创建可以用插入来实现(复杂度O(nlogn)),也可以使用数组直接转换成堆(复杂度O(n))。
  5. 假设数组长度为n,那么这个数组转成堆,需要从第一个有子节点的节点((n - 1)/2或(n - 2)/2开始,倒序“调整堆”,直到下标为0。
  6. 插入操作可以先将数据插入到数组尾部,然后依次调整该数据的父节点,父节点的父节点......直到根节点。
  7. 删除操作可以先将数组首尾节点互换,然后删除最后面的元素,最后再调整根节点即可。

3.0 代码实现

3.1使用swift实现

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

/*
 * 堆
 */
class Heap<T: Comparable> {
    private var _arr: [T];
    private var _type: HeapType;
    
    /*
     * 使用数组创建堆
     * @param {[T]} - arr 创建堆的数组
     * @param {HeapType} - type 堆类型
     */
    init(arr: [T], type: HeapType = .big) {
        self._arr = arr;
        self._type = type;
        self._create();
    }
    
    /*
     * 调整堆:调整以idx为顶的3元素子堆,若顶部元素不是最大/最小,则调整为最大/最小
     * @param {Int} - idx 表示调整以idx为顶的3元素子堆
     * @return {Bool} - 调整成功返回true,无需调整返回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;
    }
    
    /**
     * 创建堆,依次调整 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);
        }
    }
    
    /**
     * 弹出一个元素,移除顶部元素,然后令顶部元素等于最后一个元素,最后调整顶部元素
     * @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;
    }
    
    /**
     * 插入一个元素,插入到尾部,依次调整该元素的顶部元素,直到无需调整或下标为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);
        }
    }
    
    /**
     * 返回当前元素数量
     * @return {Int} 返回堆内元素数量
     */
    func count() -> Int{
        return _arr.count;
    }
}
复制代码

3.2使用js实现

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

//构造函数
function Heap(type, arr, compareFunction){
    this.type = type;
    this.arr = arr;
    this.compareFunction = compareFunction;
    this._createHeap(arr);
}

//数组交换
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;
            }
        }
    }
}

//调整堆的第i个结点
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;
    //左值存在并且大于根结点
    if(leftValue && this._compare(leftValue, arr[i])){
        //右值存在并且大于左结点
        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);
        //交换完毕后,新的子结点也需要调整
        this._adjustNode(exchangeIdx, arr);
    }
}

//根据数组创建堆
Heap.prototype._createHeap = function(arr){
    let len = arr.length;
    if(len <= 1){
        return;
    }
    //最后一个非叶子结点
    let lastNonLeafIdx = Math.floor(len / 2) - 1;
    //依次调整每个结点
    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 复杂度分析

  1. 数组转堆的复杂度
    • 首先需要进行n/2次堆的调整
    • 每次调整堆最多可能需要 logn次的二次调整
      • 所以时间复杂度小于 O(nlogn)
    • 每次调整堆最少可能需要1次调整
      • 所以时间复杂度大于O(n/2)
    • 实际上,需要少量调整的操作数远远大于需要多次调整的操作。
      • 根据调整规则,设最高高度为h = logn
      • 根节点需要调整次数为:2^0*h
      • 第二层需要调整次数为:2^1*(h-1)
      • ... ...
      • 第logn层需要调整次数为:2^(h-1)*1
      • 总次数count=2^0*h + 2^1*(h-1) + 2^2*(h-2) + ... + 2^(h-1)*(h-(h-1)) //使用错位相减
      • 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
      • 所以时间复杂度为O(n)
  2. 堆的插入:O(logn)
  3. 堆的删除:O(logn)
关注下面的标签,发现更多相似文章
评论