原创

大根堆的创建-java版本

温馨提示:
本文最后更新于 2022年08月28日,已超过 37 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我

一、介绍

大根堆就是所有父结点都比它的左右孩子大。
存储结构:采用数组进行存储,同完全二叉树的存储一样。
数组从0开始则:2i+1为左孩子,2i+2为右孩子。
数组从1开始则:2i为左孩子,2i+1为右孩子。

二、算法思想

  1. 若数组长度为n,根据完全二叉树的性质可知:
    (1)1到n/2 为父结点
    (2)n/2+1到n为叶子节点
  2. 叶子结点不需要调整,只需要保证父结点比左右孩子结点大即可。
  3. 从最后一个父结点向前进行调整,保证每一个父结点比左右孩子大。
  4. 如果从第一个父结点进行调整无法找到最大的一个结点。

三、算法实现

    /**
     *
     * @param arr
     * @param k 需要调整的堆结点
     * @param len 数组的长度
     */
    void heapAdjust(int arr[],int k,int len) {
        int temp = arr[k]; // 暂存需要调整的结点,避免被覆盖
        // i指向k的左孩子结点
        for(int i = 2*k+1;i <len;i++) {
            // i<len保证k有右孩子;同时将i指向较大的一个结点
            if(i < len-1 && arr[i]<arr[i+1]) {
                i++;
            }
            // 父节点和孩子结点相同或者父节点大于孩子结点则跳出该次循环
            if(arr[i] <= temp) {
                break;
            } else {  // 孩子结点大于父结点则进行调整
                arr[k] = arr[i];  // 将孩子结点放到父节点出
                k = i;  // 父节点重新指向
            }
        }
        arr[k] = temp; // 初始父节点k(arr[0])找到了合适的位置
    }
    @Test
    public void buildHeap(){
        int a[] = {32,45,17,65,53,9,78,87};
        System.out.println("原始数组:\n"+Arrays.toString(a));
        int len = a.length;
        for (int i = len/2 ; i >=0 ; i--) {
            heapAdjust(a,i,len);
        }
        System.out.println("大根堆:\n"+Arrays.toString(a));
    }

四、运行结果

file

正文到此结束
本文目录