大顶堆(小顶堆同理可推)

1.大顶堆 :

 逻辑结构:

             1颗完全二叉树,结点的值大于其左右两个字节点的值。

存储结构:

             单一结点值的可以使用数组存储。例如数组int[] a从 下标1开始存储结点值。则 大顶堆满足 a[i] = a[2 * i],a[i] = a[2 * i +1]


2.建大顶堆

  2.1主要方法maxHeapify(int[] a,int i):

          以i为根结点,递归  向下调整整棵树,使其满足大顶堆的定义 a[i] = a[2 * i],a[i] = a[2 * i +1]。

  2.2 从最大非叶子结点 (下标为 nodeNum /2,nodeNum 为树的总结点数 )从后往前调用maxHeap(int[] a,int i )方法,从小到大,慢慢将整棵树调整为大顶堆。

   java示例代码:

package hank.sort;
/**
 * 大顶堆逻辑上是  树形结构,实际存储以数组形式存放
 * @author zhouhuakang
 *
 */
public class HeapSort {
	public static void main(String[] args){
		//a[0] 存放数组中从下标1开始存放的数字个数
		int[] a = {10,4,1,3,2,16,9,10,14,8,7};
		HeapSort heapSort = new HeapSort();
		heapSort.buildMaxHeap(a);
		for (int i = 1; i  a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}
	/**
	 * 
	 * @param a a[0] 存放数组中 1 -
	 */
	public void buildMaxHeap(int a[]){
		for(int i = a[0] / 2 ;i =1; i--){
			maxHeapify(a, i);
		}
	}
	/**
	 * 调整以i为根节点的树,使其成为大顶堆
	 * @param a 下标0存储 树 节点的个数
	 * @param i
	 */
	public void maxHeapify(int a[],int i){
		int nodeNum = a[0];
		int l = i * 2;
		int r = i * 2 + 1;
		int largest;
		// 根 左 右  三者比较大小,larget指向最大者,首先l与i比较,largest得出较大者,然后r与largest比较,较大者为最大者
		if(l = nodeNum   a[l]  a[i]){
			largest = l;
		}else {
			largest = i;
		}
		if( r = nodeNum  a[r]  a[largest]){
			largest = r;
		}
		// 左右子树 有一个结点的值 大于根结点
		if(largest != i){
			int temp =  a[largest];
			a[largest] = a[i];
			a[i] = temp;
			// 递归向下调整
			maxHeapify(a, largest);
		}
		
	}

}


参考:

1.推荐阅读《挑战程序设计竞赛2》

  

 

最新回复(0)
/jishuZsBgu_2BGx_2BZOMQMGwnMQsfGdgP2ypyR2z_2F4PmlQ_3D_3D4834074
8 简首页