小根堆的实现

  1. package util;
  3. import java.util.Arrays;
  4. import java.util.Random;
  6. public class Heap {
  7.     // 实际大小
  8.     private int size;
  10.     // 最大容量
  11.     private int capacity;
  13.     // 数据
  14.     int[] data;
  17.     /**
  18.      * 初始化
  19.      */
  20.     public Heap() {
  21.         size = 0;
  22.         capacity = 100;
  23.         data = new int[capacity];
  24.     }
  26.     /**
  27.      * 指定初始容量初始化
  28.      *
  29.      * @param capacity 初始容量
  30.      */
  31.     public Heap(int capacity) {
  32.         size = 0;
  33.         this.capacity = capacity;
  34.         data = new int[capacity];
  35.     }
  37.     /**
  38.      * 向下堆化
  39.      *
  40.      * @param i 起始位置
  41.      */
  42.     private void fixDown(int i) {
  43.         int num = data[i];
  44.         int son = i * 2 + 1;
  45.         while ((son < size)) {
  46.             if ((son + 1 < size) && (data[son] > data[son + 1])) {
  47.                 ++son;
  48.             }
  49.             if (num < data[son]) {
  50.                 break;
  51.             }
  52.             data[i] = data[son];
  53.             i = son;
  54.             son = i * 2 + 1;
  55.         }
  56.         data[i] = num;
  57.     }
  59.     /**
  60.      * 向上堆化
  61.      *
  62.      * @param i 起始位置
  63.      */
  64.     private void fixUp(int i) {
  65.         int num = data[i];
  66.         int father = (i - 1) / 2;
  67.         while ((i > 0) && (data[father] > num)) {
  68.             data[i] = data[father];
  69.             i = father;
  70.             father = (i - 1) / 2;
  71.         }
  72.         data[i] = num;
  73.     }
  75.     /**
  76.      * 添加元素
  77.      *
  78.      * @param item 元素值
  79.      */
  80.     public void offer(int item) {
  81.         // 扩容
  82.         if (size == capacity) {
  83.             data = Arrays.copyOf(data, data.length * 2);
  84.             capacity *= 2;
  85.         }
  86.         data[size++] = item;
  87.         fixUp(size - 1);
  88.     }
  90.     /**
  91.      * 删除堆顶元素
  92.      *
  93.      * @return 原堆顶元素的值
  94.      */
  95.     public int poll() {
  96.         if (size == 0) {
  97.             throw new UnsupportedOperationException("堆为空");
  98.         }
  99.         int ans = data[0];
  100.         data[0] = data[size - 1];
  101.         --size;
  102.         fixDown(0);
  103.         return ans;
  104.     }
  106.     /**
  107.      * 堆是否为空
  108.      * @return 堆中无元素则空, 有元素则非空
  109.      */
  110.     public boolean isEmpty() {
  111.         return size == 0;
  112.     }
  114.     public static void main(String[] args) {
  115.         Heap heap = new Heap();
  116.         Random random = new Random();
  117.         for (int i = 0; i < 500; ++i) {
  118.             heap.offer(random.nextInt(1000));
  119.         }
  120.         while (!heap.isEmpty()) {
  121.             System.out.println(heap.poll());
  122.         }
  123.     }
  124. }