堆的基本概念

末蓝、 2022-10-24 05:54 133阅读 0赞

## 堆是什么 ##

1.是一种特殊的二叉树（完全二叉树）  
2.通过数组的方式顺序存储  
3.对于这个数的任意节点来说，满足根节点大于左右子树的值（大堆），或者任意一节点满足根节点的值小于左右子树的值（小堆）

## 堆能干啥 ##

1.能高效得找出一个集合的最大/最小元素（堆顶元素）  
2.能高效得找到前K大/前K小的元素（topk问题）

## 核心操作 ##

**向下调整 & 向上调整**

1.向下调整（以大根堆为例）

时间复杂度：O(logN) (size固定，child每次乘以2)

//按照大堆来实现
    
        //向下调整
    
        //size ☞ array中那部分内容为堆
        //index ☞ 从哪个位置开始向下调整
        //如果父节点的下标为i，左子树的下标为2*i+1，右子树的下标为2*i+2
        //子节点的下标为i，父节点的下标为（i-1）/2
        public static void shiftDown(int[] array, int size, int index){
        
            int parent = index;
            int child = parent * 2 + 1;
            while (child < size){
        
                //里面的条件的含义，是看看parent有没有子节点
                //把左右子树中较大的节点
                if (child + 1 < size && array[child+1] > array[child]){
        
                    child = child+1;
                }
                //上述完成后，child一定是最大的元素
                if (array[child] > array[parent]){
        
                    //需要交换
                    int tmp = array[child];
                    array[child] = array[parent];
                    array[parent] = tmp;
                }else {
        
                    //说明当前位置开始已经符合堆的要求了
                    break;
                }
                parent = child;
                child = 2*parent+1;
            }
        }
    
        public static void createHeap(int[] array, int size){
        
            //基于向下调整
            //建堆可以基于向下调整和向上调整
            //如果是向下调整，就需要从后往前遍历数组
            for (int i = (size - 1 - 1)/2; i>= 1; i--){
        
                shiftDown(array,size,i);
            }
        }
    
        public static void main(String[] args) {
        
            int[] array = {
        9,5,2,7,3,6,8};
            createHeap(array,array.length);
            System.out.println(Arrays.toString(array));
        }

2.向上调整

//向上调整
        
        //此时size这个参数其实不需要用到，判断是否调整完了只需要和0比较就行了
    
        private int[] array = new int[100];
        private int size = 0;
        public static void shiftUp(int[] array, int size, int index){
        
            int child = index;
            int parent = (child - 1)/2;
            while (child > 0){
        
                if (array[parent] < array[child]){
        
                    //当前不符合大堆要求
                    int tmp = array[parent];
                    array[parent] = array[child];
                    array[child] = tmp;
                }else {
        
                    break;
                }
                child = parent;
                parent = (child - 1) / 2;
            }
        }

## 添加/删除/取堆顶元素 ##

1）添加元素（使用向上调整）

private int[] array = new int[100];
        private int size = 0;
    
        public void offer(int x){
        
            //新加的元素放到了数组的最后，把这个新加的节点就弄成child
            array[size] = x;
            size++;
            //把新加入的元素进行向上调整
            shiftUp(array,size - 1);
        }
    
        public static void shiftUp(int[] array, int index){
        
            int child = index;
            int parent = (child - 1)/2;
            while (child > 0){
        
                if (array[parent] < array[child]){
        
                    //当前不符合大堆要求
                    int tmp = array[parent];
                    array[parent] = array[child];
                    array[child] = tmp;
                }else {
        
                    break;
                }
                child = parent;
                parent = (child - 1) / 2;
            }
        }

2）删除元素（使用向下调整）

public int poll(){
        
            //下标为0的元素就是队首元素，删掉的同时，剩下的队列也是堆
            //要删除堆顶元素，直接把数组中的最后一个元素给赋值到堆顶元素
            //同时 size-- 就把元素删掉了
            int oldValue = array[0];
            array[0] = array[size-1];
            size--;
            shiftDown(array,size,0);
            return oldValue;
        }
        public static void shiftDown(int[] array, int size, int index){
        
            int parent = index;
            int child = parent * 2 + 1;
            while (child < size){
        
                //里面的条件的含义，是看看parent有没有子节点
                //把左右子树中较大的节点
                if (child + 1 < size && array[child+1] > array[child]){
        
                    child = child+1;
                }
                //上述完成后，child一定是最大的元素
                if (array[child] > array[parent]){
        
                    //需要交换
                    int tmp = array[child];
                    array[child] = array[parent];
                    array[parent] = tmp;
                }else {
        
                    //说明当前位置开始已经符合堆的要求了
                    break;
                }
                parent = child;
                child = 2*parent+1;
            }
        }

3）取堆顶元素

public int peek(){
        
            return array[0];
        }

## 标准库中的优先队列 ##

import java.util.PriorityQueue;
    
    public class TestPriorityQueue {
        
        //标准库的优先队列(默认为小堆)
        public static void main(String[] args) {
        
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            queue.offer(9);
            queue.offer(5);
            queue.offer(2);
            queue.offer(7);
            queue.offer(3);
            queue.offer(6);
            while (!queue.isEmpty()){
        
                int cur = queue.poll();
                System.out.println(cur);
            }
    
        }
    
    }