Java語(yǔ)言如何實(shí)現(xiàn)最大堆

這篇文章將為大家詳細(xì)講解有關(guān)Java語(yǔ)言如何實(shí)現(xiàn)最大堆，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

成都創(chuàng)新互聯(lián)公司是一家專業(yè)提供松嶺企業(yè)網(wǎng)站建設(shè),專注與做網(wǎng)站、成都網(wǎng)站建設(shè)、成都h5網(wǎng)站建設(shè)、小程序制作等業(yè)務(wù)。10年已為松嶺眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)絡(luò)公司優(yōu)惠進(jìn)行中。

最大堆

最大堆的特點(diǎn)是父元素比子元素大，并且是一棵完全二叉樹。

data[1]開始存，data[0]空著不用。也可以把data[0]當(dāng)成size來(lái)用。

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對(duì)比)
   */
	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對(duì)比)
   */
	public T popMax() {
		swap(1, size--);
		shiftDown(1);
		return data[size + 1];
	}
	/**
   * @param child 孩子節(jié)點(diǎn)下角標(biāo)是child，父節(jié)點(diǎn)下角表是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數(shù)組中某個(gè)元素的下角標(biāo)
   * @param b data數(shù)組中某個(gè)元素的下角標(biāo)
   * @return 哪個(gè)元素大就返回哪個(gè)的下角標(biāo)
   */
	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數(shù)組中某個(gè)元素的下角標(biāo)
   * @param b data數(shù)組中某個(gè)元素的下角標(biāo)
   * @param c data數(shù)組中某個(gè)元素的下角標(biāo)
   * @return 哪個(gè)元素大就返回哪個(gè)的下角標(biāo)
   */
	private int max(int a, int b, int c) {
		int biggest = max(a, b);
		biggest = max(biggest, c);
		return biggest;
	}
	/**
   * @param father 父節(jié)點(diǎn)下角標(biāo)是father,左右兩個(gè)孩子節(jié)點(diǎn)的下角表分別是：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即將更新，父、左、右三個(gè)結(jié)點(diǎn)誰(shuí)大，newFather就是誰(shuí)的下角標(biāo)
			if (lchild > size) {
				//如果該father結(jié)點(diǎn)既沒有左孩子，也沒有右孩子
				return;
			} else if (rchild > size) {
				//如果該father結(jié)點(diǎn)只有左孩子，沒有右孩子
				newFather = max(father, lchild);
			} else {
				//如果該father結(jié)點(diǎn)既有左孩子，又有右孩子
				newFather = max(father, lchild, rchild);
			}
			if (newFather == father) {
				//說明father比兩個(gè)子結(jié)點(diǎn)都要大，表名已經(jīng)是大根堆，不用繼續(xù)調(diào)整了
				return;
			} else {
				//否則，還需要繼續(xù)調(diào)整堆，直到滿足大根堆條件為止
				swap(father, newFather);
				//值進(jìn)行交換
				father = newFather;
				//更新father的值，相當(dāng)于繼續(xù)調(diào)整shiftDown(newFather)
			}
		}
	}
	public static void main(String[] args) {
		//創(chuàng)建大根堆
		MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
		//向堆里存
		for (int i = 0; i < 100; i++) {
			maxHeap.insert((int) (Math.random() * 100));
		}
		//創(chuàng)建數(shù)組
		Integer[] arr = new Integer[100];
		//從堆里取，放進(jìn)數(shù)組里
		for (int i = 0; i < 100; i++) {
			arr[i] = maxHeap.popMax();
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
}

最大堆：shiftDown()函數(shù)與上面不一樣

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對(duì)比)
   */
	public T popMax() {
		T ret = data[1];
		swap(1, size);
		size--;
		shiftDown(1);
		return ret;
	}
	/**
   * @return 查看最大根(只看不刪, 與popMax對(duì)比)
   */
	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]兩者取大的那個(gè)
				newFather = newFather + 1;
			}
			if (data[father].compareTo(data[newFather]) >= 0) {
				break;
			} else {
				swap(father, newFather);
				//值進(jìn)行交換
				father = newFather;
				//newFather是(2*father)或者是(2*father+1),也就是繼續(xù)shiftDown(newFather);
			}
		}
	}
	public static void main(String[] args) {
		//創(chuàng)建大根堆
		MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
		//向堆里存
		for (int i = 0; i < 100; i++) {
			maxHeap.insert((int) (Math.random() * 100));
		}
		//創(chuàng)建數(shù)組
		Integer[] arr = new Integer[100];
		//從堆里取，放進(jìn)數(shù)組里
		for (int i = 0; i < 100; i++) {
			arr[i] = maxHeap.popMax();
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
}

關(guān)于“Java語(yǔ)言如何實(shí)現(xiàn)最大堆”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。

分享名稱：Java語(yǔ)言如何實(shí)現(xiàn)最大堆
分享URL：http://muchs.cn/article26/ipiicg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供、企業(yè)網(wǎng)站制作、軟件開發(fā)、電子商務(wù)、用戶體驗(yàn)、網(wǎng)站維護(hù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

搜索引擎優(yōu)化