定义
- 是一颗完全二叉树
- 每一个结点都大于等于它的子结点（大顶堆），或者小于等于它的子结点（小顶堆）
图解
堆树.png
堆的插入过程
- 从下往上
- 从上往下
其插入的过程就叫做堆化
从下往上.png
堆的删除过程
删除_1.png
删除_2.png
初始化堆的过程
初始化堆_1.png
初始化堆_2.png
代码实现
public class HeapTree { private int[] arr; public HeapTree() { } public HeapTree(int capacity) { arr = new int[capacity]; } /** * 堆化方法 * * @param start {@code int} 化堆结点 * @param end {@code int} 化堆结束点 */ public void heapIndex(int start, int end) { int parent = start; while (parent * 2 + 1 < end) { int son = parent * 2 + 1; if (son + 1 < end && arr[son + 1] < arr[son]) { son = son + 1; } if (arr[son] < arr[parent]) { int temp = arr[son]; arr[son] = arr[parent]; arr[parent] = temp; } parent = son; } } /** * 排序 */ public void sort() { for (int i = arr.length - 1; i > 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapIndex(0, i); } } /** * 创建堆 * * @param arr {@code int[]} 初始堆 */ public void createHeap(int[] arr) { this.arr = arr; int len = arr.length; for (int i = len / 2 - 1; i >= 0; i--) { heapIndex(i, len); } } /** * top K 问题 * * @param number */ public void topK(int number) { if (number < arr[0]) { return; } arr[0] = number; heapIndex(0, arr.length); } public static void main(String[] args) { int[] arr = {30, 23, 17, 18, 5, 10}; HeapTree heapTree = new HeapTree(); heapTree.createHeap(arr); heapTree.sort(); System.out.println(Arrays.toString(arr)); } }
TOP K 问题
给你1亿个的数字（整数，1~2^32-1），求出前10大的数字，还可动态添加新数字。
public class TopKOfNumber { public static void main(String[] args) { HeapTree heapTree = new HeapTree(10); long startTime = System.currentTimeMillis(); final Random random = new Random(); int[] arr = new int[10]; //初始化堆 for (int i = 0; i < 10; i++) { arr[i] = Math.abs(random.nextInt()); } heapTree.createHeap(arr); for (int i = 0; i < 100000000; i++) { int number = random.nextInt(); heapTree.topK(number); } heapTree.topK(Integer.MAX_VALUE); System.out.println(Arrays.toString(arr)); System.out.println("共花费时间: " + (System.currentTimeMillis() - startTime) + "ms"); } }
