| import java.util.*; | |
| /** | |
| * K-Heapsort | |
| * k-heapsort | |
| * | |
| * Sorts an almost-sorted array, wherein every element is no more than k units from its sorted position, in O(n log k) time. | |
| * | |
| * Input: | |
| * arr: A list of ints | |
| * k: an int indicating the maximum displacement of an element in arr from its final sorted location | |
| * | |
| * Preconditions: | |
| * The elements of arr are unique. | |
| * Each element in arr is at most k places from its sorted position. | |
| * | |
| * Output: | |
| * A generator that yields the elements of arr in sorted order | |
| * | |
| * Example: | |
| * >>> list(kheapsort([3, 2, 1, 5, 4], 2)) | |
| * [1, 2, 3, 4, 5] | |
| * >>> list(kheapsort([5, 4, 3, 2, 1], 4)) | |
| * [1, 2, 3, 4, 5] | |
| * >>> list(kheapsort([1, 2, 3, 4, 5], 0)) | |
| * [1, 2, 3, 4, 5] | |
| * | |
| * @author derricklin | |
| */ | |
| public class KHEAPSORT { | |
| // import heapq | |
| // heap is data structure used for priority queue | |
| // pq O(log n) to pull off lowest priority item | |
| // heap is a type of binary tree | |
| // every node its value smaller than everything below it | |
| // priority queue in java is least-value first (at head) | |
| public static ArrayList<Integer> kheapsort(ArrayList<Integer> arr, int k) { | |
| PriorityQueue<Integer> heap = new PriorityQueue<Integer>(); | |
| for (Integer v : arr.subList(0,k)) { | |
| heap.add(v); | |
| } | |
| ArrayList<Integer> output = new ArrayList<Integer>(); | |
| for (Integer x : arr.subList(k, arr.size())) { | |
| heap.add(x); | |
| Integer popped = heap.poll(); | |
| output.add(popped); | |
| } | |
| while (!heap.isEmpty()) { | |
| output.add(heap.poll()); | |
| } | |
| return output; | |
| } | |
| } | |