6.堆

1、堆数据结构是一种数组对象。

2、该数组对象的两个属性：

length【A】数组元素的个数

heap-size【A】存放在A中的堆的元素个数

3、父节点与其左右子节点的关系：

父节点：parent（i）

return i/2;

             左子节点：getLeftChild(i)

return 2*i+1;

     右子节点：getRightChild（i）

return 2*i+2;

4、最大堆的特性：(堆排序)

A[PARENT(i)]>=A[i];

     最小堆的特性：（优先队列）

A[PARENT(i)]<=A[i];

5、堆排序：

      1.建堆：

Build_heap(A)

heap_size(A)<--length[A]

for i<--取整[length[A]/2]-1

do Max_heapify(A,i)

      2.调整堆:

Max_heapify(A,i)

left<-getLeftChild(i)

right<-getRightChild(i)

if left<=heap_size[A]&&A[left]>A[i]

then largst<-left

else  largst<-i

                if right<=heap_size[A]&&A[right]>A[i]

then largst<-right

if largst != i

then exchange A[i]<-->A[largst]

Max_heapify(A,largst)

 

      3.堆排序:

HeapSort(A)

Build_heap(A)

for i<--length[A]-1

do exchange A[0]<---heap_size[A]-1

Max_heapify(A,i)

6、Java代码实现：

public class HeapSort
{
	/**
	 * 堆排序的方法
	 * @param array
	 */
	public static void heapSort(int a[],int alen)
	{
		int hlen=alen;
		int temp;
		//1、建堆
		BuildHeap(a,hlen);
		
		for(int i=alen-1;i>=0;i--)
		{
			temp=a[0];//将数组的最后一个元素与第一个元素交换
			a[0]=a[i];
			a[i]=temp;
			hlen--;       //堆长度减1
			Max_HeapIFY(a,hlen,0);//调整堆
		}
		
	}
	/**
	 * 建堆的方法
	 */
	public static void BuildHeap(int a[],int hlen)
	{
		int begin=hlen/2-1;
		for(int i=begin;i>=0;i--)
		{
			Max_HeapIFY(a,hlen,i);	
		}
	}
	/**
	 * 调整堆的方法
	 */
	public static void Max_HeapIFY(int a[],int hlen,int i)
	{
		int left=getLeftChild(i);
		int right=getRightChild(i);
		int largst =i;
		int temp;
		
		if(left<hlen&&a[largst]<a[left])
		{
			largst=left;
		}
		if(right<hlen&&a[largst]<a[right])
		{
			largst=right;
		}
		if(i!=largst)
		{
			temp=a[largst];   //将值最大的数与当前数交换
			a[largst]=a[i];
			a[i]=temp;
			//在获取当前的左右孩子节点
			Max_HeapIFY(a,hlen,largst);
		}
	}
	/**
	 * 获取左孩子节点
	 */
	public static int getLeftChild(int i)
	{
		return 2*i+1;
	}
	public static int getRightChild(int i)
	{
		return 2*i+2;
	}
	
	public static void main(String[] args)
	{
		int a[]={16,4,10,14,7,9,3,2,8,5,1,5,33,45,323,2323,876};
		int alen=a.length;
		//未排序的顺序
		System.out.println("未排序时，数组元素的顺序：");
		for(int i=0;i<alen;i++)
		{
			System.out.print(a[i]+"  ");
		} 
		System.out.println();
		System.out.println("排序后，数组元素的顺序：");
		heapSort(a,alen);
		//排序后的顺序
		for(int i=0;i<alen;i++)
		{
			System.out.print(a[i]+"  ");
		}
		System.out.println();
		System.out.println("数组中最大的十个数为：");
		for(int i=alen-1;i>=alen-10;i--)
		{
			System.out.print(a[i]+"  ");
		}	
	}
}