- package 树;
- import 接口.Heap;
- //一个大根堆的简单实现
- public class MyHeap<T extends Comparable> implements Heap<T> {
- private final int DEFAULT_CAPACITY = 10;//初始容量
- private int count;//计数器,表示当前元素的数目
- private T[] contents;//数组,存储堆的数据
- //构造器,初始化
- public MyHeap() {
- count = 0;
- contents = (T[]) (new Comparable[DEFAULT_CAPACITY]);
- }
- //实现heap接口的add方法
- public void add(T element) {
- //如果数组已满则扩大数组
- if (count == contents.length) {
- expandCapacity();
- }
- //将元素添加到尾部
- contents[count] = element;
- //当前指向
- int current = count;
- //调整堆
- while (current > 0
- && element.compareTo(contents[getParent(current)]) > 0) {
- swap(current, getParent(current));
- current = getParent(current);
- }
- count++;
- }
- //实现heap接口的remove方法
- public T remove() {
- T result = null;
- if (count > 0) {
- //删除根,并将尾部元素作为根
- result = contents[0];
- count--;
- swap(0, count);
- contents[count] = null;
- //调整堆
- int current = 0;
- while (current != getReplace(current)) {
- swap(current, getReplace(current));
- current = getReplace(current);
- }
- }
- return result;
- }
- //倍增数组
- private void expandCapacity() {
- T[] larger = (T[]) (new Object[contents.length * 2]);
- for (int i = 0; i < contents.length; i++) {
- larger[i] = contents[i];
- }
- contents = larger;
- }
- //得到父节点索引
- private int getParent(int n) {
- return n % 2 == 0 ? n / 2 - 1 : n / 2;
- }
- //交换
- private void swap(int i, int j) {
- T temp = contents[i];
- contents[i] = contents[j];
- contents[j] = temp;
- }
- //得到可替代的索引,用于重建堆的调整
- private int getReplace(int n) {
- int result = n;
- if (contents[2 * n + 2] != null) {
- result = contents[2 * n + 1].compareTo(contents[2 * n + 2]) > 0 ? (2 * n + 1)
- : (2 * n + 2);
- result = contents[n].compareTo(contents[result]) > 0 ? n : result;
- }
- if (contents[2 * n + 2] == null && contents[2 * n + 1] != null) {
- result = contents[n].compareTo(contents[2 * n + 1]) > 0 ? n
- : (2 * n + 1);
- }
- return result;
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/110320148971.html
来源: http://www.codesnippet.cn/detail/110320148971.html