Java语言实现最大堆代码示例

最大堆

最大堆的特点是父元素比子元素大，并且是一棵完全二叉树。

data[1]开始存，data[0]空着不用。也可以把data[0]当成size来用。

public class maxheap<t extends comparable<? super t>> {
	private t[] data;
	private int size;
	private int capacity;
	public maxheap(int capacity) {
		this.data = (t[]) new comparable[capacity + 1];
		size = 0;
		this.capacity = capacity;
	}
	public int size() {
		return this.size;
	}
	public boolean isempty() {
		return size == 0;
	}
	public int getcapacity() {
		return this.capacity;
	}
	/**
   * @return 查看最大根(只看不删, 与popmax对比)
   */
	public t seekmax() {
		return data[1];
	}
	public void swap(int i, int j) {
		if (i != j) {
			t temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}
	public void insert(t item) {
		size++;
		data[size] = item;
		shiftup(size);
	}
	/**
   * @return 弹出最大根(弹出意味着删除, 与seekmax对比)
   */
	public t popmax() {
		swap(1, size--);
		shiftdown(1);
		return data[size + 1];
	}
	/**
   * @param child 孩子节点下角标是child，父节点下角表是child/2
   */
	public void shiftup(int child) {
		while (child > 1 && data[child].compareto(data[child / 2]) > 0) {
			swap(child, child / 2);
			child = child / 2;
		}
	}
	/**
   * @param a data数组中某个元素的下角标
   * @param b data数组中某个元素的下角标
   * @return 哪个元素大就返回哪个的下角标
   */
	private int max(int a, int b) {
		if (data[a].compareto(data[b]) < 0) {
			//如果data[b]大
			return b;
			//返回b
		} else {
			//如果data[a]大
			return a;
			//返回a
		}
	}
	/**
   * @param a data数组中某个元素的下角标
   * @param b data数组中某个元素的下角标
   * @param c data数组中某个元素的下角标
   * @return 哪个元素大就返回哪个的下角标
   */
	private int max(int a, int b, int c) {
		int biggest = max(a, b);
		biggest = max(biggest, c);
		return biggest;
	}
	/**
   * @param father 父节点下角标是father,左右两个孩子节点的下角表分别是：father*2 和 father*2+1
   */
	public void shiftdown(int father) {
		while (true) {
			int lchild = father * 2;
			//左孩子
			int rchild = father * 2 + 1;
			//右孩子
			int newfather = father;
			//newfather即将更新，父、左、右三个结点谁大，newfather就是谁的下角标
			if (lchild > size) {
				//如果该father结点既没有左孩子，也没有右孩子
				return;
			} else if (rchild > size) {
				//如果该father结点只有左孩子，没有右孩子
				newfather = max(father, lchild);
			} else {
				//如果该father结点既有左孩子，又有右孩子
				newfather = max(father, lchild, rchild);
			}
			if (newfather == father) {
				//说明father比两个子结点都要大，表名已经是大根堆，不用继续调整了
				return;
			} else {
				//否则，还需要继续调整堆，直到满足大根堆条件为止
				swap(father, newfather);
				//值进行交换
				father = newfather;
				//更新father的值，相当于继续调整shiftdown(newfather)
			}
		}
	}
	public static void main(string[] args) {
		//创建大根堆
		maxheap<integer> maxheap = new maxheap<integer>(100);
		//向堆里存
		for (int i = 0; i < 100; i++) {
			maxheap.insert((int) (math.random() * 100));
		}
		//创建数组
		integer[] arr = new integer[100];
		//从堆里取，放进数组里
		for (int i = 0; i < 100; i++) {
			arr[i] = maxheap.popmax();
			system.out.print(arr[i] + " ");
		}
		system.out.println();
	}
}

最大堆：shiftdown()函数与上面不一样

public class maxheap<t extends comparable<? super t>> {
	private t[] data;
	private int size;
	private int capacity;
	public maxheap(int capacity) {
		data = (t[]) new comparable[capacity + 1];
		this.capacity = capacity;
		size = 0;
	}
	public int size() {
		return size;
	}
	public boolean isempty() {
		return size == 0;
	}
	public void insert(t item) {
		data[size + 1] = item;
		size++;
		shiftup(size);
	}
	/**
   * @return 弹出最大根(弹出意味着删除, 与seekmax对比)
   */
	public t popmax() {
		t ret = data[1];
		swap(1, size);
		size--;
		shiftdown(1);
		return ret;
	}
	/**
   * @return 查看最大根(只看不删, 与popmax对比)
   */
	public t seekmax() {
		return data[1];
	}
	public void swap(int i, int j) {
		if (i != j) {
			t temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}
	public void shiftup(int k) {
		while (k > 1 && data[k / 2].compareto(data[k]) < 0) {
			swap(k, k / 2);
			k /= 2;
		}
	}
	public void shiftdown(int father) {
		while (2 * father <= size) {
			int newfather = 2 * father;
			if (newfather + 1 <= size && data[newfather + 1].compareto(data[newfather]) > 0) {
				//data[j] data[j+1]两者取大的那个
				newfather = newfather + 1;
			}
			if (data[father].compareto(data[newfather]) >= 0) {
				break;
			} else {
				swap(father, newfather);
				//值进行交换
				father = newfather;
				//newfather是(2*father)或者是(2*father+1),也就是继续shiftdown(newfather);
			}
		}
	}
	public static void main(string[] args) {
		//创建大根堆
		maxheap<integer> maxheap = new maxheap<integer>(100);
		//向堆里存
		for (int i = 0; i < 100; i++) {
			maxheap.insert((int) (math.random() * 100));
		}
		//创建数组
		integer[] arr = new integer[100];
		//从堆里取，放进数组里
		for (int i = 0; i < 100; i++) {
			arr[i] = maxheap.popmax();
			system.out.print(arr[i] + " ");
		}
		system.out.println();
	}
}

总结

以上就是本文关于java语言实现最大堆代码示例的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！