大小堆

二叉树的性质：

大小堆虽然是用数组存储的数据结构，但是其思想用到了完全二叉树的性质，因此需要知道这些内容：

满二叉树的定义：

在一棵二叉树中，如果所有的分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

完全二叉树的定义：

对一棵具有n个结点的二叉树按层序编号，如果编号为$i(1≤i≤n)$的结点与同样深度的满二叉树中编号为$i$的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

性质1：

在二叉数的第$i$层至多有$2^{i-1}$个结点

性质2：

深度为k的二叉树至多有$2^{k}-1$个结点($k≥1$)

性质3：

对任何一棵二叉树T,如果其终端节点数为$n_0$,度为2的结点数为$n_2$,则$n_0=n_2+1$

推理过程：

  • 假设$n_0$是度为$0$的结点数，假设$n_1$是度为$1$的结点数,假设$n_2$是度为$2$的结点数,则树T的总结点数：$n=n_0+n_1+n_2$
  • $n_1$和$n_2$因为分别有一个节点和两个节点，因此总根数：$n_1+2*n_2$
  • 除了根节点以外，每个节点都有一个对应的分支，因此总根数：$n-1$
  • 可以推的：$n-1 = n_1 + 2 * n_2 => n_0+n_1+n_2-1=n_1 + 2 * n_2 => n_0 = n_2 + 1$

性质4：

具有n个结点的完全二叉树的深度为$\lfloor{log_2^n}\rfloor + 1(\lfloor{x}\rfloor 表示不大于x的最大整数)$

推理：

  • 深度为$k$的完全二叉树满足$2^{k-1}-1≤n≤2^{k}-1$,可以推的$2^{k-1}≤n＜2^k$，可以推的$k-1≤log_2^n＜k$,k作为整数，因此$k=\lfloor{log_2^n}\rfloor + 1(\lfloor{x}\rfloor 表示不大于x的最大整数)$

性质5:

如果对一棵有n个结点的完全二叉树(其深度为$\lfloor{log_2^n}\rfloor + 1(\lfloor{x}\rfloor 表示不大于x的最大整数)$)的结点按层序编号(从第1层到$\lfloor{log_2^n}\rfloor + 1$，每层从左到右)，对任一结点$i(1≤i≤n)$有：

  1. 如果$i=1$，则结点$i$是二叉树的根，无双亲;如果$i>1$，则其双亲是结点$\lfloor{i/2}\rfloor$
  2. 如果$2i＞n$，则结点$i$无左孩子(结点$i$为叶子结点);否则其左孩子是结点$2i$
  3. 如果$2i+1＞n$，则结点$i$无右孩子;否则其右孩子是结点$2i+1$

大小堆的定义：

堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆，或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树 的顺序存储方式存储在一个一维数组中，并满足：$k_i≤k_{2i+1}且k_i≤k_{2i+2}(k_i≥k_{2i+1}且k_1≥k_{2i+2}) i=0,1,2...$ 且 ，则称这个堆为最小堆(或最大堆)。

最大堆：

思路：

  1. 声明一个数组heap存储元素，声明两个变量limit和size，分别表示堆的容量和大小
  2. 根据堆和完全二叉树的定义，可以知道结点$i$的左右子节点必然在数组$2i+1$和$2i+2$上
  3. 声明一个方法push，表示插入元素，首先将元素插入到末尾，然后执行heapInsert方法，size++
    1. heapInsert方法参考的堆的结点$i$的左右子节点必然在数组$2i+1$和$2i+2$上，
      1. 那么当前结点$j$如果是左结点，则父节点$(j-1)/2$，
      2. 如果当前结点$j$是右结点，则直接$(j-1)/2 = (2*i +2 - 1)/2 =i-1/2$,int类型整数除2，直接向下取整，因此等于$i$,
      3. 所以左右结点$j$的父节点必然是$(j-1) / 2$
    2. heapInsert方法的参数是数组$arr$和$index$，$arr$表示当前堆数组，$index$表示当前插入数组的位置
      1. 拿$index$和它的父节点$(index-1)/2$的元素比较,$arr[index] > arr[(index-1)/2]$，则将$arr[index]$和$arr[(index-1)/2]$上的元素交换，然后$index = (index-1)/2$,继续上一次的比较，直到比父亲元素小，或者到$0$位置
private void swap(int[] arr,int i,int j){
    int tmp = arr[i];
    int arr[i] = arr[j];
    int arr[j] = tmp;
}

private void heapInsert(int[] arr,int index){
    while(arr[index] > arr[(index-1)/2]){
        swap(arr,index,(index-1)/2);
        index = (index-1)/2;
    }
}

public void push(int value){
    if(this.heapSize == this.limit){
        throw new RunTimeException("heap is full");
    }
    heap[heapSize] == value;
    heapInsert(arr,heapSize++);
}

  1. 声明一个方法pop,表示弹出最大值，首先得到$ans = arr[0]$的值，然后拿$0$和$heapSize$的元素互换，然后heapSIze--,这样就能弹出最大栈的数值，然后再调用heapify方法，将栈顶的元素向下降，放到一个合理的位置

    1. heapify方法需要三个参数，分别是数组$arr[]$,$index$,$heapSize$,
    2. 得到当前index的左节点的下标:$left：2index+1$，右节点的下标:$right:2index+2 = left + 1$
    3. 判断左右节点谁大，谁大，赋值给largest，然后largest和index判断谁元素大
      1. index大，则退出当前循环
      2. largest大，则将index和largest的元素互换，index移到largest小标处，然后得到新的left和right，重复上面过程，直到left超出heapSize范围
    private void heapify(int[] arr,int index , int heapSize){
    int left = index * 2 +1;
    while(left < heapSize){
        int largest = left+1 < heapSize && arr[left+1] > arr[left] ? left + 1 : left;
        largest = arr[largest] > arr[index] ? largest : index;
        if(largest == index){
            break;
        }
        swap(arr,largest,index);
        index = largest;
        left = index * 2+1;
    }
}

public int pop(){
    int ans = heap[0];
    swap(heap,0,--this.heapSize);
    heapify(arr,0,this.heapSize);
    return ans;
}

    完整版本:

    public class MyMaxHeap{
    private int[] heap;
    private final int limit;
    private int heapSize;

    public MyMaxHeap(int limit){
        heap = new int[limit];
        this.limit = limit;
        this.heapSize = 0;
    }

 	private void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        int arr[i] = arr[j];
        int arr[j] = tmp;
    }

    private void heapInsert(int[] arr,int index){
        while(arr[index] > arr[(index - 1)/2]){
            swap(arr,index,(index-1)/2);
            index = (index - 1)/2;
        }
    }

    public void push(int value){
        if(this.heapSize == this.limit){
            return new RuntimeException("heap is full");
        }
        heap[heapSize]=value;
        heapInsert(heap,heapSize++);
    }

    private int heapify(int[] arr,int index,int heapSize){
        int left = index * 2+1;
        while(left < heapSize){
            int target = left + 1 < heapSize : arr[left + 1] > arr[left] ? left+1:left;
            largest = arr[largest] > arr[index] ? largest : index;
            if(largest == index){
                break;
            }
            swap(arr,largest,index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    public int pop(){
        if(heapSize == 0){
            throw new RunTimeException("No element");
        }
        int ans = this.heap[0];
        swap(heap,0,--this.heapSize);
        heapify(heap,0,this.heapSize);
        return ans;
    }

    public boolean isEmpty(){
        return this.heapSize == 0;
    }

    public boolean isFull(){
        return this.heapSize == this.limit;
    }
}

加强堆

定义：给堆中的元素增加一张反向索引表，记录入堆元素的位置，通过反向索引表知道堆中元素的位置，随后，不管调整还是删除元素，只需要在它的当前位置进行heapInsert或者heapify操作就可以了。

public class HeapGrater<T>{
    private ArrayList<T> heap;
    private HashMap<T,Integer> indexMap;
    private int heapSize;
    private Comparator<? super T> comp;
    
    public HeapGrater(Comparator<? super T> C){
        heap = new ArrayList<>();
        indexMap = new HashMap<>();
        heapSize = 0;
        comp = c;
    }
    /**
    交换i和j位置的元素，同时把变化对应的i，j更新到indexMap
    */
    private void swap(int i,int j){
        T o1 = heap.get(i);
        T o2 = heap.get(j);
        indexMap.put(o1,j);
        indexMap.put(o2,i);
        heap.set(i,o2);
        heap.set(j,o1);
    }
    
    /**
    比较子元素和父元素之间的关系，小于0，子元素<父元素，交换位置
    */
    private void heapInsert(int index){
        while(comp.compare(heap.get(index),heap.get((index-1)/2))<0){
            swap(index,(index-1)/2);
            index = (index-1)/2;
        }
    }
    
    /**
    先在heap里添加一个元素，然后indexMap更新这个元素位置,heapInsert方法会更新obj的位置和对应的indexMap
    */
    public void push(T obj){
        heap.add(obj);
        indexMap.put(obj,heapSize);
        heapInsert(heapSize++);
    }
    
    /**
    1.比较左右两个叶子结点元素的大小，拿最小的和index做比较
    2.如果index小，就退出当前循环
    3.如果index大，就和较小的结点元素互换位置，然后index更新为较小结点的位置，继续循环
    */
    private void heapify(int index){
        int left = index *2+1;
        while(left < heapSize){
            int target = left+1<heapSize && comp.compare(heap.get(left+1),heap.get(left)) < 0?left+1:left;
            target = comp.compare(heap.get(index),heap.get(left)) < 0 ? index : left;
            if(index == target){
                break;
            }
            swap(index,target);
            index = target;
            left = 2 * index + 1;
        }
    }
    
    /**
    1.返回头节点元素ans
    2.将头节点元素和最后一个元素互换位置，然后indexMap去除ans和对应的索引位置，heap去掉最后一位元素
    3.将头节点元素往下沉
    */
    public T pop(){
        T ans = heap.get(0);
        swap(0,heapSize-1);
        indexMap.remove(ans);
        heap.remove(--heapSize);
        heapify(0);
        return ans;
    }
    
    public  void resign(T obj){
        int index = indexMap.get(obj);
        heapInsert(index);
        heapify(index);
    }
    
    /**
    类似pop方法
    1.获取heap数组的最后一个元素：replace
    2.通过indexMap,得到obj的在heap中的数组位置，index
    3.indexMap去除obj和对应的索引
    4.heap去除最后一个元素
    5.如果obj不是最后一个元素，则将index位置上填上replace，indexMap记录replace位置，然后重新对replace做resign操作
    */
    public void remove(T obj){
        
        /*
        int index = indexMap.get(obj);
        T rep = heap.get(heapSize-1);
        swap(index,heapSize-1);
        indexMap.remove(obj);
        heap.remove(--heapSize);
        resign(rep);
        */
        T replace = heap.get(heapSize - 1);
        int index = indexMap.get(obj);
        indexMap.remove(obj);
        heap.remove(--heapSize);
        if(replace != obj){
            heap.set(index,replace);
            indexMap.put(replace,index);
            resign(replace);
        }
    }
    
    public T peek(){
        return heap.get(0);
    }
    
    public boolean isEmpty(){
        return heapSize == 0;
    }
    
    public int size(){
        return heapSize;
    }
    
    public boolean contains(T obj){
        return indexMap.containKey(obj);
    }
}

堆排序

定义：将待排序的数组构造成一个大顶堆。此时，整个数组的最大值就是堆顶的根结点。将根节点和末尾元素互换，然后将$n-1$个元素重新构造成一个堆，这样就会得到$n$个元素中的次大值。反复执行，便能得到一个有序数组了。

public void heapSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    /*
    for(int i = 0;i < arr.length;i++){
        heapInsert(arr,i);
    }
    */
    
    for(int i = arr.length-1;i>=0;i++){
        heapify(arr,i,arr.length);
    }
    
    int heapSize = arr.length;
    swap(arr,0,--heapSize);
    
    while(heapSize > 0){
        heapify(arr,0,heapSize);
        swap(arr,0,--heapSize);
    }
    
}

private void heapify(int[] arr,int index , int heapSize){
    int left = index * 2 +1;
    while(left < heapSize){
        int largest = left+1 < heapSize && arr[left+1] > arr[left] ? left + 1 : left;
        largest = arr[largest] > arr[index] ? largest : index;
        if(largest == index){
            break;
        }
        swap(arr,largest,index);
        index = largest;
        left = index * 2+1;
    }
}

private void heapInsert(int[] arr,int index){
    while(arr[index] > arr[(index-1)/2]){
        swap(arr,index,(index-1)/2);
        index = (index-1)/2;
    }
}

private void swap(int[] arr,int i,int j){
    int tmp = arr[i];
    int arr[i] = arr[j];
    int arr[j] = tmp;
}

排序元素移动小于k的数组

问题：已知一个几乎有序的数组(几乎有序是指如果把数组排好序的话，每个元素移动的距离不超过k，且k相较于数组而言较小).请选择一个合适的排序算法对这个数据进行排序

思路：

  1. 声明一个优先级队列(默认小根堆)，存储数组的前k个元素，前k个元素的最小值就可以得到。
  2. 然后弹出第一个元素，得到k个元素中的最小值，放到数组i（初始0）中，然后i++,然后队列放入数组k+1个元素，然后弹出。
  3. 上述过程，反复执行，最后把队列中剩余元素放入数组中，即是一个有序的数组。
public void sortedArrDistanceLessK(int[] arr,int k){
    if(k == 0){
        return;
    }
    PriorityQueue<Integer> queue = new PriorityQueue<>();
    int index = 0
    for(;index <= Math.min(arr.length-1,k-1);index++){
        queue.add(arr[index]);
    }
    int i = 0;
    for(; index < arr.length;i++,index++){
        queue.add(arr[index]);
        arr[i] = queue.poll();
    }
    
    while(!queue.isEmpty()){
        arr[i++] = queue.poll();
    }
}

最大线段重合问题

题目：给定很多线段，每个线段有两个整数[begin,end]，表示一条线段的起始位置和结束位置（end大于begin且都非负） 规定：重合区域必须大于等于1：例如[1,4]和[4,5]就不算重合 输入一个二维数组，数组的每个元素是一个包含两个元素的数组，分别为每个线段begin和end 返回线段最多重合区域中线段的个数 例如 arr = [[1,3],[2,4],[4,8]] 返回2,因为在[2,3]这个范围内有2个连段重合

思路：

一：

  1. 求出当前所有线段最小的起始位置min和最大的结束位置max
  2. 求min到max之间每一段(一段距离为1，因此可以表示成这段的起点+1)，有多少数组经过，然后取经过最多的数组返回

二：对当前数组进行排序，起始位置升序排列，这样，只要求每个线段的起始位置有多少个结束位置大于他的线段，就能求出当前的最大线段数

public class Code01_CoverMax{
    //方法一
    public static int maxCover1(int[][] lines){
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i = 0;i<lines.length;i++){
            min = Math.min(min,lines[i][0]);
            max = Math.max(max,lines[i][1]);
        }
        int cover = 0;
        for(double p = min + 0.5;p < max;p++){
            int cur = 0;
            for(int i = 0;i < lines.length;i++){
                if(lines[i][0] < p && lines[i][1] > p){
                    cur++;
                }
            }
            cover = Math.max(cur,cover);
        }
        return cover;
    }
    
    public static class Line{
        public int start;
        public int end;
        
        public Line(int s,int e){
            start = s;
            end = e;
        }
    }
    
    //方法二
    public static int maxCover2(int[][] lines){
        Line[] lineArr = new Line[lines.length];
        for(int i = 0;i<lines.length;i++){
            lineArr[i] = new Line(lines[i][0],lines[i][1]);
        }
        Arrays.sort(lineArr,new Comparator<Line>(){
            @Override
            public int compare(Line o1,Line o2){
                return o1.start - o2.start;
            }
        });
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int max = 0;
        for(Line line : lineArr){
            while(!heap.isEmpty && heap.peek() <line.start){
                heap.poll();
            }
            heap.add(line.end);
            max = Math.max(max,heap.size());
        }
        return max;
    }
    
    //方法三
    public static int maxCover3(int[][] lines){
        Arrarys.sort(lines,(a,b) -> a[0] - b[0] );
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int max = 0;
        for(int i = 0;i < lines.length;i++){
            while(!heap.isEmpth && heap,peek() < lines[i][0]){
                heap.poll();
            }
            heap.add(lines[i][1]);
            max = Math.max(max,heap.size());
        }
        return max;
    }
    
    public static int[][] genericLines(int N,int L,int R){
        int size = (int)(Math.random()*N)+1;
        int[][] lineArr = new int[Size][2];
        for(int i = 0;i < siez;i++){
            int a = L + (int)(Math.random()*(R - L + 1));
            int b = L + (int)(Math.random()*(R - L + 1));
            if(a == b){
                if(a!=R){
                    b = a+1;
                } else {
                    a = a - 1;
                }
            }
            lines[i][0] = Math.min(a,b);
            lines[i][1] = Math.max(a,b);
        }
        return lines;
    }
    
    public static void main(String[] args) {
        System.out.println("test begin");
        int N = 200;
        int L = 0;
        int R = 200;
        int testTimes = 20000;
        for(int i = 0;i<testTimes;i++){
            int[][] lineArr = genericLines(N,L,R);
            int ans1 = maxCover1(lineArr);
            int ans2 = maxCover2(lineArr);
            int ans3 = maxCover3(lineArr);
            if(ans != ans2 || ans1 != ans3){
                System.out.println("Oops");
            }
        }
        System.out.println("test end");
    }
}