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

java;">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();	}}

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();	}}