heapify

// Version Linpz
public class Solution {
    /**
     * @param A: Given an integer array
     * @return: void
     */
    private void siftdown(int[] A, int k) {
        while (k * 2 + 1 < A.length) {
            int son = k * 2 + 1;
            if (k * 2 + 2 < A.length && A[son] > A[k * 2 + 2])
                son = k * 2 + 2;
            if (A[son] >= A[k])
                break;

            int temp = A[son];
            A[son] = A[k];
            A[k] = temp;
            k = son;
        }
    }

    public void heapify(int[] A) {
        for (int i = (A.length - 1) / 2; i >= 0; i--) {
            siftdown(A, i);
        }
    }
}

// Version 1: this cost O(n)
public class Solution {
    /**
     * @param A: Given an integer array
     * @return: void
     */
    private void siftdown(int[] A, int k) {
        while (k < A.length) {
            int smallest = k;
            if (k * 2 + 1 < A.length && A[k * 2 + 1] < A[smallest]) {
                smallest = k * 2 + 1;
            }
            if (k * 2 + 2 < A.length && A[k * 2 + 2] < A[smallest]) {
                smallest = k * 2 + 2;
            }
            if (smallest == k) {
                break;
            }
            int temp = A[smallest];
            A[smallest] = A[k];
            A[k] = temp;

            k = smallest;
        }
    }

    public void heapify(int[] A) {
        for (int i = A.length / 2; i >= 0; i--) {
            siftdown(A, i);
        } // for
    }
}


// Version 2: This cost O(nlogn)
public class Solution {
    /**
     * @param A: Given an integer array
     * @return: void
     */
    private void siftup(int[] A, int k) {
        while (k != 0) {
            int father = (k - 1) / 2;
            if (A[k] > A[father]) {
                break;
            }
            int temp = A[k];
            A[k] = A[father];
            A[father] = temp;

            k = father;
        }
    }

    public void heapify(int[] A) {
        for (int i = 0; i < A.length; i++) {
            siftup(A, i);
        }
    }
}

ugly number ii

     public int nthUglyNumber(int n) {

         PriorityQueue<Integer> pq = new PriorityQueue<>();
         Set<Integer> set = new HashSet<>();
         int[] prime = new int[] {2,3,5};
         pq.add(1);
         for (int i = 0; i < 3; i++) {
             pq.add(prime[i]);
             set.add(prime[i]);
         }

         int rst = 0;
         for (int i = 0; i < n - 1; i++) {
             rst = pq.poll();
             for (int j = 0; j < 3; j++) {
                if (set.contains(rst * prime[j]) 
                    || rst > Integer.MAX_VALUE / prime[j]) continue;
                pq.add(rst * prime[j]);
                set.add(rst*prime[j]);
             }
         }

         return pq.peek();
     }

top k largest number ii

public class Solution {
    private int maxSize;
    private Queue<Integer> minheap;
    public Solution(int k) {
        minheap = new PriorityQueue<>();
        maxSize = k;
    }

    public void add(int num) {
        if (minheap.size() < maxSize) {
            minheap.offer(num);
            return;
        }

        if (num > minheap.peek()) {
            minheap.poll();
            minheap.offer(num);
        }
    }

    public List<Integer> topk() {
        Iterator it = minheap.iterator();
        List<Integer> result = new ArrayList<Integer>();
        while (it.hasNext()) {
            result.add((Integer) it.next());
        }
        Collections.sort(result, Collections.reverseOrder());
        return result;
    }
};

data stream median

    public int[] medianII(int[] nums) {  
        // write your code here  
        if(nums==null) return null;  
        int[] res = new int[nums.length];  

        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();  
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11, new Comparator<Integer>() {  
            @Override  
            public int compare(Integer x, Integer y) {  
                return y-x;  
            }  
        });  
        res[0] = nums[0];  
        maxHeap.add(nums[0]);  

        for(int i=1; i<nums.length; i++) {  
            int x = maxHeap.peek();  
            if(nums[i] <= x) {  
                maxHeap.add(nums[i]);  
            } else {  
                minHeap.add(nums[i]);  
            }  

              while (minHeap.size() >= maxHeap.size() + 1) {  
                maxHeap.offer(minHeap.poll());
              }
              while (maxHeap.size() > minHeap.size() + 1) {
                minHeap.offer(maxHeap.poll());
              }
              res[i] = maxHeap.peek();  
        }  
        return res;  
    }

kth smallest numbers in matrix

• min heap
• pop() * k

public class Solution {
    /**
     * @param matrix: a matrix of integers
     * @param k: an integer
     * @return: the kth smallest number in the matrix
     */
    public int kthSmallest(int[][] matrix, int k) {
        // write your code here

        int rows = matrix.length;
        int cols = matrix[0].length;

        PriorityQueue<Point> pq = new PriorityQueue<Point>(k, new PointComparator());
        for (int i = 0; i < rows; i++) {
            pq.offer(new Point(i, 0, matrix[i][0]));
        }

        for (int i = 0; i < k - 1; i++) {
            Point p = pq.poll();
            if (p.col == cols - 1) {
                continue;
            }
            pq.offer(new Point(p.row, p.col+1, matrix[p.row][p.col+1]));
        }

        return pq.poll().val;
    }
}

class Point {
    int row, col, val;

    public Point(int row, int col, int val) {
        this.row = row;
        this.col = col;
        this.val = val;
    }
}

class PointComparator implements Comparator<Point> {
    public int compare(Point A, Point B) {
        return A.val - B.val;
    }
}

data stream median

• maxHeap - normal class, hold small part numbers. always have equal or one more element. when odd, maxHeap.peek()
• minHeap - top class, hold larger part numbers. when even, (minHeap.peek() + maxHeap.peek()) / 2
• adjust minHeap and maxHeap
  • when size are different -> move to minHeap
  • when coming largest in maxHeap is larger than smallest in minHeap && minHeap is not null -> swap

class MedianFinder {

    /** initialize your data structure here. */
    PriorityQueue<Integer> maxHeap;
    PriorityQueue<Integer> minHeap;
    int count;

    public MedianFinder() {
        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>((v1, v2) -> v2 - v1);
        count = 0;
    }

    public void addNum(int num) {
        count = (count + 1) % 2;
        maxHeap.offer(num);

        if (minHeap.size() > 0) {
            if (minHeap.peek() < maxHeap.peek()) {
                minHeap.offer(maxHeap.poll());
                maxHeap.offer(minHeap.poll());
            }
        }

        if (maxHeap.size() - minHeap.size() > 1) {
            minHeap.offer(maxHeap.poll());
        }        
    }

    public double findMedian() {
        if (count == 1) 
            return maxHeap.peek();
        else 
            return (maxHeap.peek() + minHeap.peek()) / 2.0;        
    }
}

    PriorityQueue<Integer> minHeap = new PriorityQueue<>();//heap is a minimal heap by default
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());//change to a maximum heap

// Adds a number into the data structure.
public void addNum(int num) {
    maxHeap.offer(num);
    minHeap.offer(maxHeap.poll());
    if (maxHeap.size() < minHeap.size())
        maxHeap.offer(minHeap.poll());
}

// Returns the median of current data stream
public double findMedian() {
    if (maxHeap.size() == minHeap.size())
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    else
        return maxHeap.peek();
}

sliding window median

approach i: minHeap and maxHeap

• • notice: remove element
  • O(nk), remove(num) is O(k)
• approach ii: treeSet
  • O(nlogk)
  • use treeSet instead of PriorityQueue, notice to dedup, use Node(index, num[index])
• TreeSet vs Heap
  • TreeSet remove is O(logn), Heap is O(n)
  • Add, both are O(logn)
  • TreeSet does not allow duplicate

public class Solution {
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>((v1,v2) -> v2.compareTo(v1)); // v2-v1 will exceed limit

    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length - k + 1;
        if (n <= 0) return new double[0];
        double[] result = new double[n];

        for (int i = 0; i < nums.length; i++) {
            add(nums[i]);
            if (i >= k) remove(nums[i-k]);
            if (i + 1 >= k) result[i+1-k] = getMedian();            
        }

        return result;
    }

    private void add(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());

        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    private void remove(int num) {
        if (maxHeap.contains(num)) {
            maxHeap.remove(num);
        }
        else {
            minHeap.remove(num);        
        }

        if (minHeap.size() > maxHeap.size()) {  // when remove from maxHeap, maxHeap may have one less elements
            maxHeap.offer(minHeap.poll());
        }

        if (maxHeap.size() - minHeap.size() > 1) {  // when remove from minHeap, maxHeap may have two more elements
            minHeap.offer(maxHeap.poll());
        }
    }

    private double getMedian() {
        if (maxHeap.isEmpty() && minHeap.isEmpty()) return 0;

        if (maxHeap.size() == minHeap.size()) {
            return ((double)maxHeap.peek() + (double)minHeap.peek()) / 2.0;
        }
        else {
            return (double)maxHeap.peek();
        }
    }
}

sliding window maximum:

• deque

sliding window template

Maximum Average Subarray I

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int sum = 0;
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (i - k >= 0) sum -= nums[i-k];
            if (i - k + 1 >= 0) max = Math.max(max, sum);
        }

        return (double) max/k;        
    }
}

Maximum Average Subarray ii

• ??