114°

聊聊算法--堆的构建和调整

先提个问题,完全二叉树/满二叉树,区别?前者是指每一层都是紧凑靠左排列,最后一层可能未排满,后者是一种特殊的完全二叉树,

每层都是满的,即节点总数和深度满足N=(2^n) -1。堆Heap,一堆苹果,为了卖相好,越好看的越往上放,就是大顶堆;为了苹果堆

的稳定,质量越小越往上放,就是小顶堆;堆首先是完全二叉树,但只确保父节点和子节点大小逻辑,不关心左右子节点的大小关系,

通常是一个可以被看做一棵树的数组对象,是个很常见的结构,比如BST对象,都与堆有关系,今天就说下这个重要的数据结构和应用。

 

作者原创文章,谢绝一切转载,违者必究!

本文只发表在"公众号"和"博客园",其他均属复制粘贴!如果觉得排版不清晰,请查看公众号文章。 

 

准备:

Idea2019.03/Gradle6.0.1/Maven3.6.3/JDK11.0.4

难度: 新手--战士--老兵--大师

目标:

1.堆的构建和调整算法

1 优先级队列

为理解堆的原理,先看优先级队列,它是一种数据结构,插入或者删除元素的时候,元素会自动排序,(优先级不是狭义的数值大小,

但为了通俗理解,这里以字母序为例),通常使用数组存储,我们可以按照下图进行转换,序号 0 不用:

优先级队列的实现(Java版):

public class PriorityQueue<Key extends Character> {
    /** 存储元素的数组 */
    private Key[] keys;
    private int N = 0;
</span><span style="color: #0000ff;">public</span> PriorityQueue(<span style="color: #0000ff;">int</span><span style="color: #000000;"> capacity){
    </span><span style="color: #008000;">//</span><span style="color: #008000;"> 下标0不用,多分配一个单位</span>
    keys = (Key[]) <span style="color: #0000ff;">new</span> Character[capacity + 1<span style="color: #000000;">];
}

</span><span style="color: #0000ff;">public</span><span style="color: #000000;"> Key max(){
    </span><span style="color: #0000ff;">return</span> keys[1<span style="color: #000000;">];
}

</span><span style="color: #0000ff;">public</span> <span style="color: #0000ff;">void</span><span style="color: #000000;"> insert(Key e){
    N </span>++<span style="color: #000000;">;
    keys[N] </span>=<span style="color: #000000;"> e;
    swim(N);
}
</span><span style="color: #0000ff;">public</span><span style="color: #000000;"> Key delMax(){
    Key max </span>= keys[1<span style="color: #000000;">];
    swap(</span>1<span style="color: #000000;">,N);
    keys[N] </span>= <span style="color: #0000ff;">null</span><span style="color: #000000;">;
    N </span>--<span style="color: #000000;">;
    </span><span style="color: #008000;">//</span><span style="color: #008000;"> 让第一个元素下沉到合适的位置</span>
    sink(1<span style="color: #000000;">);
    </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> max;
}
</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 上浮第k个元素</span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">void</span> swim(<span style="color: #0000ff;">int</span><span style="color: #000000;"> k){
    </span><span style="color: #008000;">//</span><span style="color: #008000;"> 比父节点小,即进行交换,直到根</span>
    <span style="color: #0000ff;">while</span> (k &gt; 1 &amp;&amp;<span style="color: #000000;"> less(parent(k),k)){
        swap(k,parent(k));
        k </span>=<span style="color: #000000;"> parent(k);
    }
}
</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 下沉第 k 个元素</span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">void</span> sink(<span style="color: #0000ff;">int</span><span style="color: #000000;"> k){
    </span><span style="color: #0000ff;">while</span>(k &lt;<span style="color: #000000;"> N){
        </span><span style="color: #0000ff;">int</span> small =<span style="color: #000000;"> left(k);
        </span><span style="color: #0000ff;">if</span> (right(k) &lt; N &amp;&amp;<span style="color: #000000;"> less(right(k),left(k))){
            small </span>=<span style="color: #000000;"> right(k);
        }
        </span><span style="color: #0000ff;">if</span><span style="color: #000000;"> (less(k,small)){
            swap(k,small);
            k </span>=<span style="color: #000000;"> small;
        }
    }
}
</span><span style="color: #0000ff;">private</span> <span style="color: #0000ff;">void</span> swap(<span style="color: #0000ff;">int</span> i,<span style="color: #0000ff;">int</span><span style="color: #000000;"> j){
    Key temp </span>=<span style="color: #000000;"> keys[i];
    keys[i] </span>=<span style="color: #000000;"> keys[j];
    keys[j] </span>=<span style="color: #000000;"> temp;
}
</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 元素i和j大小比较</span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">boolean</span> less(<span style="color: #0000ff;">int</span> i,<span style="color: #0000ff;">int</span><span style="color: #000000;"> j){

// 'a' - 'b' = -1 ; return keys[i].compareTo(keys[j]) > 0; } / 元素i的父节点*/ private int parent(int i){ return i/2; } / 元素i的左子节点/ private int left(int i){ return i * 2; } /** 元素i的右子节点/ private int right(int i){ return i * 2 + 1; } }

 

以上代码解析:

1 swim 上浮,对于元素k,是否需要上浮,仅需与其父节点比较,大于父节点则交换,迭代直到根节点;

2 sink 下沉,对于元素k,是否需要下沉,需先比较其左右子节点,找出左右子节点中较小者,较小者若比父节点大,则交换,迭代直到末尾元素;

3 insert 插入,先将元素放到数组末尾位置,再对其进行上浮操作,直到合适位置;

4 delMax 删除最大值,大根堆,故第一个元素最大,先将首末元素交换,再删除末尾元素,再对首元素下沉操作,直到合适位置;

总结:以上只是Java简化版,java.util.PriorityQueue 是JDK原版,客官可自行研究。但设计还是非常有技巧的,值得思考一番,假设 insert 插入

到首位,会导致数组大量元素移动。delMax 若直接删除首位最大值,则需要进一步判断左右子节点大小,并进行先子节点上浮再首元素下沉操作。

        有了这个堆结构,就可以进行堆排序了,将待排数全部加入此堆结构,然后依次取出,即成有序序列了!

2 堆排序

如要求不使用上述堆数据结构。思路(升序为例):将数组构建为一个大顶堆,首元素即为数组最大值,首尾元素交换;排除末尾元素后调整大顶堆,

则新的首元素即为次最大值,交换首尾并再排除末尾元素;如此循环,最后的数组即为升序排列

public class HeapSort02 {
    public static void main(String []args){
        int []arr = {2,1,8,6,4,7,3,0,9,5};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
</span><span style="color: #0000ff;">public</span> <span style="color: #0000ff;">static</span> <span style="color: #0000ff;">void</span> sort(<span style="color: #0000ff;">int</span><span style="color: #000000;"> []arr){
    </span><span style="color: #0000ff;">int</span> len =<span style="color: #000000;"> arr.length;
    </span><span style="color: #008000;">//</span><span style="color: #008000;"> 创建一个大顶堆</span>
    <span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> i = (<span style="color: #0000ff;">int</span>) Math.ceil(len/2 - 1); i &gt;= 0; i--<span style="color: #000000;">){
        </span><span style="color: #008000;">//</span><span style="color: #008000;">从第一个非叶子结点从下至上,从右至左调整结构</span>

adjustHeap(arr,i,len); } // 交换首尾元素,并重新调整大顶堆 for(int j = len-1;j > 0;j--){ swap(arr,0,j); adjustHeap(arr,0,j); } }

</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 迭代写法</span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">public</span> <span style="color: #0000ff;">static</span> <span style="color: #0000ff;">void</span> adjustHeap(<span style="color: #0000ff;">int</span> []arr,<span style="color: #0000ff;">int</span> i,<span style="color: #0000ff;">int</span><span style="color: #000000;"> length){
    </span><span style="color: #0000ff;">int</span> temp =<span style="color: #000000;"> arr[i];
    </span><span style="color: #0000ff;">for</span> (<span style="color: #0000ff;">int</span> k = 2*i + 1; k &lt; length; k=k*2 + 1<span style="color: #000000;">) {
    </span><span style="color: #008000;">//</span><span style="color: #008000;"> 注意这里的k + 1 &lt; length
        </span><span style="color: #008000;">//</span><span style="color: #008000;"> 如果右子节点大于左子节点,则比较对象为右子节点</span>
        <span style="color: #0000ff;">if</span> (k + 1 &lt; length &amp;&amp; arr[k] &lt; arr[k+1<span style="color: #000000;">]){
            k</span>++<span style="color: #000000;">;
        }
        </span><span style="color: #0000ff;">if</span> (arr[k] &gt;<span style="color: #000000;"> temp){
            </span><span style="color: #008000;">//</span><span style="color: #008000;"> 不进行值交换</span>
            arr[i] =<span style="color: #000000;"> arr[k];
            i </span>=<span style="color: #000000;"> k;
        }
        </span><span style="color: #0000ff;">else</span><span style="color: #000000;">{
            </span><span style="color: #0000ff;">break</span><span style="color: #000000;">;
        }
    }
    arr[i] </span>=<span style="color: #000000;"> temp;
}

</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 递归写法</span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">static</span> <span style="color: #0000ff;">void</span> adjustHeap2(<span style="color: #0000ff;">int</span>[] arr, <span style="color: #0000ff;">int</span> i, <span style="color: #0000ff;">int</span><span style="color: #000000;"> len){
    </span><span style="color: #0000ff;">int</span> left = 2 * i + 1<span style="color: #000000;">;
    </span><span style="color: #0000ff;">int</span> right = 2 * i + 2<span style="color: #000000;">;
    </span><span style="color: #0000ff;">int</span> maxIndex =<span style="color: #000000;"> i;
    </span><span style="color: #008000;">//</span><span style="color: #008000;"> 注意这里的 left &lt; len</span>
    <span style="color: #0000ff;">if</span> (left &lt; len &amp;&amp; arr[left] &gt;<span style="color: #000000;"> arr[maxIndex]){
        maxIndex </span>=<span style="color: #000000;"> left;
    }
    </span><span style="color: #0000ff;">if</span> (right &lt; len &amp;&amp; arr[right] &gt;<span style="color: #000000;"> arr[maxIndex]){
        maxIndex </span>=<span style="color: #000000;"> right;
    }
    </span><span style="color: #0000ff;">if</span> (maxIndex !=<span style="color: #000000;"> i){
        swap(arr,i,maxIndex);
        adjustHeap2(arr,maxIndex,len);
    }
}

</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 交换元素 </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">public</span> <span style="color: #0000ff;">static</span> <span style="color: #0000ff;">void</span> swap(<span style="color: #0000ff;">int</span> []arr,<span style="color: #0000ff;">int</span> a ,<span style="color: #0000ff;">int</span><span style="color: #000000;"> b){
    </span><span style="color: #0000ff;">int</span> temp=<span style="color: #000000;">arr[a];
    arr[a] </span>=<span style="color: #000000;"> arr[b];
    arr[b] </span>=<span style="color: #000000;"> temp;
}

}

 

以上代码解析:

1完全二叉树结构中,如果根节点顺序号为 0,总节点数为 N,则最末节点的父节点即为最后一个非叶子节点,顺序号为 ceil(N/2 -1),

2 adjustHeap2 为啥使用三个参数,不用中间的参数可以?使用三个参数,是为了进行递归调用,因为递归肯定是缩小计算规模,而这里的形参arr和len是固定不变的;

3 adjustHeap是非递归写法,不用中间的参数可以?调用一在“构建大顶堆”处,可写为函数体内初始化 i,并形成双重 for 循环;调用二在“重新调整大顶堆”处,

    可见中间参数为 0,可直接去掉。故回答是可以!但需要调整写法,且影响该方法复用,这里直接写为三个形参的函数更为优雅而已。

4非递归写法理解:类似插入排序思想(依次移动并找到合适的位置再插入),先将 arr[i] 取出,然后此节点和左右子树进行比较,如子树更大则子节点上升一层,使

    用for循环迭代到最终位置,并进行赋值;

 

以 i=0 为例:

5递归方式理解:定位目标元素的左右子树,若子树值更大,则进行值交换,且因为子树发生了变化,故需要对子树进行递归处理;

3 前K个最大的数

在N个数中找出前K个最大的数: 思路:从N个数中取出前K个数,形成一个数组[K],将该数组调整为一个小顶堆,则可知堆顶为K个数中最小值,

然后依次将剩余 N-K 个数与堆顶比较,若大于,则替换掉并调整堆,直到所有元素加入完毕,堆中元素即为目标集合。

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i] = i + 1;
        }
        // 前10个最大的数
        int k = 10;
        // 构造小顶堆
        for (int i = (int) Math.ceil(k/2 - 1); i >= 0; i--) {
            adjustHeap(arr,i,k);
        }
        // 依次比较剩余元素
        for (int i = 10; i < arr.length; i++) {
            if (arr[i] > arr[0]){
                swap(arr,0,i);
                adjustHeap(arr,0,k);
            }
        }
        // 输出结果
        for (int i = 0; i < 10; i++) {
            System.out.print(arr[i]+"-");
        }
    }
</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 非迭代写法 ,对arr[i]进行调整 </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">static</span> <span style="color: #0000ff;">void</span> adjustHeap(<span style="color: #0000ff;">int</span>[] arr,<span style="color: #0000ff;">int</span> i,<span style="color: #0000ff;">int</span><span style="color: #000000;"> length){
    </span><span style="color: #0000ff;">int</span> temp =<span style="color: #000000;"> arr[i];
    </span><span style="color: #0000ff;">for</span> (<span style="color: #0000ff;">int</span> k = i * 2 + 1; k &lt; length; k = k * 2 + 1<span style="color: #000000;">) {
        </span><span style="color: #008000;">//</span><span style="color: #008000;"> 因第一次循环中可能越界,故需要 k+1 &lt; length</span>
        <span style="color: #0000ff;">if</span> (k + 1 &lt; length &amp;&amp; arr[k] &gt; arr[k + 1<span style="color: #000000;">]){
            k</span>++<span style="color: #000000;">;
        }
        </span><span style="color: #0000ff;">if</span> (arr[k] &lt;<span style="color: #000000;"> temp){
            arr[i] </span>=<span style="color: #000000;"> arr[k];
            i </span>=<span style="color: #000000;"> k;
        }
        </span><span style="color: #0000ff;">else</span><span style="color: #000000;"> {
            </span><span style="color: #0000ff;">break</span><span style="color: #000000;">;
        }
    }
    arr[i] </span>=<span style="color: #000000;"> temp;
}
</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 递归写法 </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">static</span> <span style="color: #0000ff;">void</span> adjustHeap2(<span style="color: #0000ff;">int</span>[] arr,<span style="color: #0000ff;">int</span> i,<span style="color: #0000ff;">int</span><span style="color: #000000;"> length){
    </span><span style="color: #0000ff;">int</span> left = i * 2 + 1<span style="color: #000000;">;
    </span><span style="color: #0000ff;">int</span> right = i * 2 + 2<span style="color: #000000;">;
    </span><span style="color: #0000ff;">int</span> samller =<span style="color: #000000;"> i;
    </span><span style="color: #0000ff;">if</span> (left &lt; length &amp;&amp; arr[left] &gt;<span style="color: #000000;"> arr[samller]){
        samller </span>=<span style="color: #000000;"> right;
    }
    </span><span style="color: #0000ff;">if</span> (right &lt; length &amp;&amp; arr[right] &gt;<span style="color: #000000;"> arr[samller]){
        samller </span>=<span style="color: #000000;"> right;
    }
    </span><span style="color: #0000ff;">if</span> (samller !=<span style="color: #000000;"> i){
        swap(arr,i,samller);
        adjustHeap2(arr,samller,length);
    }
}

</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 交换元素 </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">public</span> <span style="color: #0000ff;">static</span> <span style="color: #0000ff;">void</span> swap(<span style="color: #0000ff;">int</span> []arr,<span style="color: #0000ff;">int</span> a ,<span style="color: #0000ff;">int</span><span style="color: #000000;"> b){
    </span><span style="color: #0000ff;">int</span> temp=<span style="color: #000000;">arr[a];
    arr[a] </span>=<span style="color: #000000;"> arr[b];
    arr[b] </span>=<span style="color: #000000;"> temp;
}

}

 

以上代码解析:按照"初始化—构建小顶堆—比较调整—输出结果"执行。注意for循环中,因第一次循环中未使用for语句条件判断,可能越界,故需要 k+1 < length

输出结果如下:

请看官思考,如果需求变为找出N个数中找出前K个最小的数,该如何实现? 建议动脑且动手的写一遍!因为魔鬼在细节!

全文完!


我近期其他文章:

    只写原创,敬请关注 

本文转载自博客园,原文链接:https://www.cnblogs.com/xxbiao/p/13197845.html

全部评论: 0

    我有话说: