有了Array数组类,接下来很快的,把我们刚才描述的事情用代码实现出来之后,在考虑出队和入队的操作,因为父节点要大于或小于他们的子节点。所以我们的节点要能相互比较,在Java继承Comparable类就可以了。
最大堆(MaxHeap类)
public class MaxHeap<E extends Comparable<E>> { private Array<E> data; public MaxHeap(int capacity) { data = new Array<>(capacity); } public MaxHeap() { data = new Array<>(); } //堆里的元素个数 public int size() { return data.getSize(); } //堆是否为空 public boolean isEmpty() { return data.isEmpty(); } //根据一个元素的索引,获取他父亲索引 private int parent(int index) { if (index == 0) { throw new IllegalArgumentException("index - 0 does't have parent."); } return (index - 1) / 2; } //根据一个元素的索引,获取他右孩子的索引 private int leftChild(int index) { return index * 2 + 1; } //根据一个元素的索引,获取他左孩子的索引 private int rightChild(int index) { return index * 2 + 2; } }