完全二叉堆之批量建堆

Love The Way You Lie 2023-02-21 11:54 8阅读 0赞

# 批量建堆 #

对堆的介绍请参考[数据结构之堆][Link 1]。

批量建堆（Heapify）：就是将已经存在n个元素的数组批量添加至堆中，而不是遍历数组一个一个将元素添加至堆中。

遍历数组一个一个添加元素至堆中，时间复杂度为O(nlogn)，而使用批量建堆，时间复杂度最低可以降为O(n)。

批量建堆有2种实现方法：

*  自上而下的上滤
 *  自下而上的下滤

## 自上而下的上滤 ##

自上而下的上滤类似于从第2个元素开始依次添加。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]  
代码实现如下：

for (int i = 1; i < size; i++) { 
        siftUp(i);
    }

## 自下而上的下滤 ##

自下而上的下滤类似于从最后一个非叶子节点开始往前删除。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]

代码实现如下：

for(int i = (size >> 1) - 1; i >= 0; i--) { 
        siftDown(i);
    }

## 效率对比 ##

自上而下的上滤的时间复杂度为所有节点的深度之和，n个节点的深度都是O(logn)，所以时间复杂度为O(nlogn)。

自下而上的下滤的时间复杂度为所有节点的高度之和，时间复杂度为O(n)。

下面是对自下而上的下滤的时间复杂度为O(n)的论证：

假设是一颗满二叉树，节点总个数为n，树高为h，那么有n=2^h−1
    设所有节点的树高之和为H(n)，那么有H(n)=2^0∗(h−0)+2^1∗(h−1)+2^2∗(h−2)+⋯+2^(h−1)∗(h−(h−1))
    H(n)= h*(2^0+2^1+2^2+ ⋯+2^(h −1)-(1∗2^1+2∗2^2+3∗2^3+ ⋯+(h−1)∗2^(h−1))
    H(n)= h∗2^(h−1)−(h−2)∗2^h+2)
    H(n)= h∗2^h−h−h∗2^h+2^(h+1)−2
    H(n)= 2^(h+1)−h−2 
    H(n)= 2∗(2^h−1)−h 
    H(n)= 2n−h 
    H(n)= 2n−log2(n+1) = O(n)
    
    S(h) = 1∗2^1+2∗2^2+3∗2^3+ ⋯+(h−1)∗2^(h−1)
    2S(h) = 2*(1∗2^1+2∗2^2+3∗2^3+ ⋯+(h−1)∗2^(h−1))= 2∗2^2+3∗2^3+ ⋯+(h−1)∗2^h
    S(h)=2S(h)-S(h)=(h−2)∗2^h+2

## 疑惑 ##

以下方法可以批量建堆么?

*  自上而下的下滤
 *  自下而上的上滤

上述方法不可行，为什么？

*  自上而下的上滤的本质为添加
 *  自下而上的下滤的本质为删除

批量建堆的代码实现如下：

public BinaryHeap(E[] data, Comparator<E> comparator) { 
            this.comparator = comparator;
            if(null == data || 0 == data.length) { 
                this.elements = (E[]) new Object[DEFAULT_CAPACITY];
            } else { 
                // 批量建堆
                int length = Integer.max(data.length, DEFAULT_CAPACITY);
                size = data.length;
                this.elements = (E[]) new Object[length];
    
                // 将元素从data复制到elements
                for (int i = 0; i < size; i++) { 
                    this.elements[i] = data[i];
                }
    
                heapify();
            }
        }
    
        private void heapify() { 
    
            // 自下而上的下滤，类似删除
            // 时间复杂度O(n)
            // (size >> 1) - 1 最后一个非叶子节点的索引
            for(int i = (size >> 1) - 1; i >= 0; i--) { 
                siftDown(i);
            }
        }

## Top K问题 ##

从n个整数中，找出最大的前k个数（k远远小于n）

*  如果使用排序算法进行全排序，需要O(nlogn)的时间复杂度（快速排序）
 *  如果使用二叉堆来解决，可以使用O(nlogk)的时间复杂度来解决

查找步骤：

*  新建一个小顶堆
 *  扫描n个整数,先将遍历到的前k个数放入堆中,从第k+1个数开始，如果大于堆顶元素，就使用replace操作（删除堆顶元素，将第k+1个数添加到堆中）
 *  扫描完毕后，堆中剩下的就是最大的前k个数

如果是找出最小的前k个数呢？用大顶堆，如果小于堆顶元素，就使用replace操作。

查找最大的前三个数的代码实现如下：

public void testTopK() { 
            int[] array = { 16, 4, 27, 32, 35, 56, 79, 88, 90};
            int k = 3;
            BinaryHeap<Integer> binaryHeap = new BinaryHeap<>((o1, o2) -> o2 - o1);
    
            for (int i = 0; i < array.length; i++) { 
                if(i < k) { 
                    binaryHeap.add(array[i]);
                } else { 
                    if(array[i] > binaryHeap.get()) { 
                        binaryHeap.replace(array[i]);
                    }
                }
            }
    
            while (!binaryHeap.isEmpty()){ 
                System.out.println(binaryHeap.remove());
            }
    
        }

更多精彩内容关注本人公众号：架构师升级之路  
![在这里插入图片描述][20200627175030665.jpg]

[Link 1]: https://blog.csdn.net/u022812849/article/details/107038143
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200630143823879.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200630143843893.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[20200627175030665.jpg]: https://img-blog.csdnimg.cn/20200627175030665.jpg