二叉堆代码,Java代码库,德仔网

代码语言

代码分类

【Java】二叉堆

作者:阿了个里 / 发布于2013/8/5/ 792

数据结构温习，PriorityQueue 背后的实现原理。做了适当简化，数组大小固定。


	public class BinaryHeap {
	 private final static int MAX = 10;
	 private int[] data = new int[MAX];
	 private int size = 0;

	 public void add(int[] data) {
	 if (data == null || data.length > 10) throw new IllegalArgumentException("Data is null or too long");

	 for (int value : data) {
	 add(value);
	 }
	 }

	 public void add(int value) {
	 checkFull();

	 int i = size;
	 if (i == 0) {
	 data[0] = value;
	 } else {
	 while (i > 0) {
	 int parent = (i - 1) >>> 1;
	 if (data[parent] <= value) break;
	 data[i] = data[parent];
	 i = parent;
	 }
	 data[i] = value;
	 }
	 size++;
	 }

	 public int take() {
	 checkEmpty();

	 int result = data[0];

	 int i = 0;
	 int half = size >>> 1;
	 while (i < half) {
	 int child = (i << 1) + 1;
	 int right = child + 1;
	 if (right < size && data[child] >= data[right]) {
	 child = right;
	 }

	 if (data[size - 1] <= data[child]) break;

	 data[i] = data[child];
	 i = child;
	 }
	 data[i] = data[size - 1];

	 size--;
	 return result;
	 }

	 private void checkEmpty() {
	 if (size == 0) throw new RuntimeException("Empty");
	 }

	 private void checkFull() {
	 if (size == MAX) throw new RuntimeException("Full");
	 }

	 public static void main(String[] args) throws Exception {
	 BinaryHeap bh = new BinaryHeap();
	 int[] data = new int[]{2, 3, 1, 5, 9, 8, 7, 6, 4};
	 bh.add(data);

	 for (int i = 0; i < data.length; i++) {
	 System.out.println(bh.take());
	 }
	 }
	}

评论列表

本站所提供的代码，版权归原作者所有，若有侵犯作者版权，请与我们联系，我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。

试试其它关键字

　二叉堆　

同语言下

可能有用的

阿了个里贡献的其它代码(2)