Heap-And-PriorityQueue

Heap & PriorityQueue 是什么

• Heap 是一种数据结构，在内存中是以 array 进行存储的； 但在逻辑上是一个 Complete Tree 的结构，并且 Tree 的中间没有气泡。
• PriorityQueue 实际上是 Java 中具有 Queue 接口的 heap 实现。毕竟是 Heap 的实现，所以它不真像 Queue 那样是 FIFO 的，每次做 poll()/ peek() 这些操作时候返回的是 min/ max 值。

Heap & PriorityQueue 支持的 operations

Heap operations:

• insert: 把新元素放入队尾之后通过堆序性比较不断往上swap，即 percolate up 的过程。 O(logn)
• update: 更新某个元素的值，之后或往上swap 或往下swap。 O(logn)
• top/get: 获得堆顶元素的值，类似peek。 O(1)
• pop: 删除堆顶元素，队尾的元素用 o(1) 时间补到堆顶去之后把它再不断往下swap，即 percolate down 的过程。O(logn)
• heapify: 把一个无序的 array 变为 heap 的过程。 O(n)

  PriorityQueue operations:

• offer(E e): 把一个新元素 insert 到 heap 的过程。 O(logn)
• 因为 PriorityQueue 这个 class 实现的是 Queue 的接口， 所以它没有 update 的功能。想要更新某个元素的值只能先拿走这个 ele，修改，再 insert 进来。
• peek(): 看一下堆顶元素的值。 O(1)
• poll(): 删除堆顶元素，队尾的元素用 o(1) 时间补到堆顶去之后把它再不断往下swap，即 percolate down 的过程。O(logn)
• remove(): 这个也是移除堆顶元素，不过 remove() 更易抛出异常。 O(logn)
• remove(E e): 移除指定元素。这是个很贵的操作，需要先 search 一遍找到这个元素再删掉。 O(n) + O(logn)
• size(): 返回一个 heap 的 size。 O(1)
• isEmpty(): O(1)

Array 实现的 Heap & BST

Array 实现的 Heap 的 operations

• Search: O(n)
• remove: O(logn)
• remove(E e): o(n + logn) -> O(n)

  BST 的 operations

• Search: O(logn)
• remove: O(logn)
• remove(E e): O(logn)

  似乎BST的时间效率更高，那为什么我们选择用 array 结构来实现 Heap 而不用 BST 来实现 Heap 呢？ / 或使用Array来实现 Heap 的好处在哪儿呢？

1. Array 数据结构的空间利用率比BST更高, 没有overhead。举例来讲: 每个ele只用存它自己就够了，不用再存个left和right。
2. Array 数据结构的物理地址连续，可以很容易的表示出来父子节点之间的 idx 关系，进而结合 3 实现风骚走位。
   a. 左孩子idx = 自己的idx * 2 + 1；
   b. 右孩子idx = 自己的idx * 2 + 2；
   c. 父节点idx = (自己的idx - 1) / 2；
3. Array 可以进行不同元素之间的 random access， Tree 结构只能 access 到它的左右孩子节点。
4. 在工业界真实情况中，往往拿到的是很多Array状的数据。对array状的数据进行heapify较简单（？）

Heap & Sort

• 想把一个无序的 array 变成具有堆序的 有两种方式：

1. 建立一个大堆/ 小堆，一个一个的把元素 offer 进 heap 里，再从堆顶一个一个打印出来 –> TC: O(n * logn) SC: O(n)
2. 对 array 进行 Heapify 操作， 再一个一个打印出来/ 反序打印出来 –> TC: O(n); SC: O(1)

   Heapify 操作是一种可以用 O(n) 时间将一个无序 array inplace 变成大堆序的操作。

• Heapify 操作的实质是： 让这个数组自行调整成一个大堆，即使之“堆有序”，且无需借助 𝑂(𝑛) 额外空间就完成了大堆的构建。
• heapify 的具体实现方法

  Reference

  link [https://www.liwei.party/2019/01/11/algorithms-and-data-structures/heapify-and-heap-sort/]

Practice 经典例题

1. K Smallest In Unsorted Array
   1.1 使用大堆做， 遍历一遍array，每次遇到比堆顶小的就更新堆 (先poll 再offer) 否则 continue. 最后poll k 次 就获得了倒序的最小的 k 个元素。

   private static int[] findKSmallest(int[] arr, int k){
       if (arr == null || k == 0) {
           return null;
       }
       // new a max heap with size k
       PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>(){
           @Override
           public int compare(Integer a, Integer b){
               if (a.equals(b)){
                   return 0;
               }
               return a.compareTo(b) > 0 ? -1 : 1;
           }
       });
       // loop through all integers
       for (int i = 0; i < arr.length; i++) {
           if (i < k) {
               maxHeap.offer(arr[i]);
           } else if (arr[i] < maxHeap.peek()) {
               maxHeap.poll();
               maxHeap.offer(arr[i]);
           } else {
               continue;
           }
       }
       int[] res = new int[k];
       if (k > arr.length) {
           for (int i = 0; i < arr.length; i++){
               res[i] = maxHeap.poll();
           }
           return res;
       }
       for (int i = 0; i < k; i++){
           int cur = maxHeap.poll();
           res[i] = cur;
       }
   
       return res;
   }
   
   public static void main(String[] args) {
       int[] array = {7,0,4,6,8,2,3,5};
       int[] result2 = findKSmallest(array, 6);
       for (Integer ele : result2) {
           System.out.println(ele);
       }
   }

   1.2 使用 quick select方法， 即用quick sort partition 对 array 进行划分，每次返回划分的 idx(代表其左 都比他小； 其右 都比他大 但并不sorted)。此方法可以通过 quick select 获得前 k 小的 elements 但是是无序的。 还需再使用 Java Arrays 自带的方法后处理。

   private static int[] KSmallest(int[] arr, int k){
       if (arr == null || k == 0) {
           return null;
       }
       quickSelect(arr, 0, arr.length - 1, k);
       // get first k elements, known k smallest but unsort. Sort first k.
       int[] res = getKEle(arr, k);
       return res;
   }
   private static void quickSelect(int[] arr, int left, int right, int k){
       // do quick sort partition
       int pivotIdx = quickSortPartition(arr, left, right);
       if (pivotIdx == k - 1) {
           return;
       } else if (pivotIdx < k - 1) {
           quickSelect(arr, pivotIdx + 1, right, k);
       } else {
           quickSelect(arr, left, pivotIdx - 1, k);
       }
   }
   private static int quickSortPartition(int[] arr, int left, int right){
       // use mid as pivot
       int pivotIdx =  left + (right - left) / 2;
       int pivotVal = arr[pivotIdx];
       // swap the pivot to tail to avoid complexity
       swap(arr, pivotIdx, right);
       // left & right, start & end both need to be maintained
       int start = left, end = right - 1;
       // start and end 需要错开才停止
       while (start <= end) {
           if (arr[start] <= pivotVal) {
               start++;
           } else if (arr[end] >= pivotVal) {
               end--;
           } else {
               // do not forget do ++/ -- after swapping
               swap(arr, start++, end--);
           }
       }
       swap(arr, right, start);
       return pivotIdx;
   }
   private static void swap(int[] arr, int a, int b){
       int temp = arr[b];
       arr[b] = arr[a];
       arr[a] = temp;
   }
   private static int[] getKEle(int[] arr, int k){
       int[] res = Arrays.copyOf(arr, k);
       Arrays.sort(res);
       return res;
   }
   public static void main(String[] args) {
       int[] array = {7,0,4,6,8,2,3,5};
       int[] result2 = KSmallest(array, 6);
       for (Integer ele : result2) {
           System.out.println(ele);
       }
   }