Sorting
Priority Queue / MinHeap or MaxHeap / TreeSet / TreeMap are good for streaming. We can use these data structures to maintain the order of existing elements and the next incoming element.
Example use: 23. Merge k Sorted Lists
QuickSort
QuickSort partition with naive pivot selection.
public int partition(int[] nums, int left, int right, int pivot) {
if(left==right) return left;
int storeIndex = left;
int pivotNum = nums[pivot];
swap(nums, pivot, right);
for(int i=left; i<right; i++) {
if(nums[i]>pivotNum) {
swap(nums, storeIndex, i);
storeIndex++;
}
}
swap(nums, storeIndex, right);
return storeIndex;
}
public void swap(int[] nums, int i, int j) {
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
Quick Select based on quick sort partition. The idea is the final index where the pivot located indicates how many elements are larger/smaller than it. If the index is k, that means the nums[pivotIndex] is the k+1 th elements in sorted order.
public int quickSelect(int[] nums, int k) {
int left = 0, right = nums.length-1;
int pivotIndex = -1;
while(left<=right && pivotIndex!=k-1) {
pivotIndex = partition(nums, left, right, left);
if(pivotIndex>k-1)
right = pivotIndex-1;
else
left = pivotIndex+1;
}
return nums[pivotIndex];
}