二叉堆及java实现

不念不忘少年蓝@ 2023-05-28 15:40 43阅读 0赞

### 基础知识 ###

本文要讲的堆不是jvm内存结构中的堆，而是一种数据结构，在jdk的优先级队列就涉及到堆这种数据结构，堆可以分为大顶堆以及小顶堆两种。下面我们来看下大顶堆等效的二叉树结构，小顶堆类似，这里就不再赘述。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3_size_16_color_FFFFFF_t_70][]

如上图所示，大顶堆的满足以下条件：

1、大顶堆等效构成的二叉树的父节点不小于其子节点

1、需要注意的是大顶堆以及小顶堆只关注每个节点与其子节点的大小，至于一个节点的子节点大小则不关注，即不是我们常说的二叉排序树。

2、上面的二叉树仅仅是大顶堆等效的一种结构，实际存储则是采用数组的形式，而不是二叉树的形式

### 实现 ###

有了大顶堆的基础知识后，接下来看下如何用java实现大顶堆的构造

public class MaxHeap {
    
        @Test
        public void test(){
            int[] array= {2,8,14,4,16,7,1,10,9,3};
            buildMaxHeap(array);
            //输出构成的大顶堆
            for(int i:array){
                println(i);
            }
        }
    
        /**
         * 初始化大顶堆
         */
        private void buildMaxHeap(int[] array){
            for(int i= (array.length-2)/2;i>=0;i--){
                maxHeapify(array,i);
            }
        }
        /**
         *
         * @param arr
         * @param i
         */
        private void maxHeapify(int[] arr,int i){
            //println("i="+i);
            //有效数据下标从0开始
            int len = arr.length;
            //左子节点
            int left = 2*i+1;
            //右子节点
            int right = 2*i+2;
            //初始化最大值节点为当前节点
            int largest = i;
            //左节点不超出数组范围且比较大节点值大，则更新较大值下标
            if(left <len && arr[left] > arr[largest]){
                //左节点比该节点大
                largest = left;
            }
            //右节点不超出数组范围且比较大节点值大，则更新较大值下标
            if(right <len && arr[right] > arr[largest]){
                //左节点比该节点大
                largest = right;
            }
            //如果子节点有一个比当前节点大，则进行数据呼唤，同时向下递归
            if(largest != i){
                //交换节点i与较大子节点数据
                swap(arr,i,largest);
                //经过上面的调整后节点i与其两个子节点满足大顶堆条件
                //但是需要判断调整后的节点largest位置以及其子节点是否还满足大顶堆特性
                maxHeepify(arr,largest);
            }
        }
    
        private void swap(int[] arr,int i,int j){
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }

上面例子对应的完全二叉树结构就如本文第一张图所示。

PS：

1、maxHeapify方法的时间复杂度为O(lgn)

2、buildMaxHeap的时间复杂度为O(n)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3_size_16_color_FFFFFF_t_70]: /images/20230528/e555351dea0c4c01b02c1b9cc1fa9f9f.png