首页 > 代码库 > 堆排序工具类(适用于top k问题,java泛型实现)
堆排序工具类(适用于top k问题,java泛型实现)
代码如下,作用如标题所述
1 public class HeapSort { 2 //方法作用:取出list里面的最小的 k 个值 3 public static <T extends Comparable<T>> List<T> sort(List<T> list, int k) throws Exception { 4 if (k <= 0) { 5 throw new Exception("k 必须大于0"); 6 } 7 if (list.size() < k) { 8 throw new Exception("list 长度必须大于k"); 9 } 10 List<T> heapList = new ArrayList<T>(k); 11 for (int i = 0; i < k; i ++) { 12 heapList.add(list.get(i)); 13 } 14 initialHeap(heapList); 15 for (int i = k; i < list.size(); i ++) { 16 if (list.get(i).compareTo(heapList.get(0)) < 0) { 17 heapList.set(0, list.get(i)); 18 heapify(heapList, k, 0); 19 } 20 } 21 return heapList; 22 } 23 private static <T extends Comparable<T>> void initialHeap(List<T> list) { 24 int n = list.size(); 25 // Build heap (rearrange array) 26 for (int i = n / 2 - 1; i >= 0; i--) 27 heapify(list, n, i); 28 } 29 private static <T extends Comparable<T>> void heapify(List<T> list, int n, int i) 30 { 31 int largest = i; // Initialize largest as root 32 int l = 2*i + 1; // left = 2*i + 1 33 int r = 2*i + 2; // right = 2*i + 2 34 35 // If left child is larger than root 36 if (l < n && (list.get(l).compareTo(list.get(largest)) > 0)) 37 largest = l; 38 39 // If right child is larger than largest so far 40 if (r < n && (list.get(r).compareTo(list.get(largest)) > 0)) 41 largest = r; 42 43 // If largest is not root 44 if (largest != i) 45 { 46 T swap = list.get(i); 47 list.set(i, list.get(largest)); 48 list.set(largest, swap); 49 // Recursively heapify the affected sub-tree 50 heapify(list, n, largest); 51 } 52 } 53 }
堆排序工具类(适用于top k问题,java泛型实现)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。