欧美vvv,亚洲第一成人在线,亚洲成人欧美日韩在线观看,日本猛少妇猛色XXXXX猛叫

文章目錄

堆的概念 堆的定義

堆可以定義為一顆二叉樹，樹的節點包含鍵（每個節點一個鍵），并且滿足下面兩個條件：

堆的形狀要求是一顆完全二叉樹，意識就是說，樹的每一層都是滿的，除了最后一層最右邊的元素可能有缺位父母優勢要求，就是說每一個節點的鍵都要大于或等于它子女的鍵。 堆的判斷

下面這個就不是堆，因為不是完全二叉樹

下面這個也不是堆，堆的節點比子節點大，4比5小

下面這個是堆

堆的特性

一顆n個節點的完全二叉樹。它的高度是:[log2n]（log以2為底，[]表示向下取整）堆的根總是包含堆的最大元素堆的一個節點以及該節點的子孫也是一個堆可以用數組來實現堆，方法是從上到下算法分析中實現堆排序c語言程序，從左到右的方式來記錄堆的元素，當有n個元素時，存放在數組的1~n的位置上。此時有：

a 父母節點會在位于數組的前n/2個位置中，而葉子節點將會在占據后n/2個位置

b 在數組中，當父母位置為i時，則子女節點會在2i和2i+1。對于一個位于i的鍵來說，它的父母節點位于i/2。 堆的構造

構造堆有兩種方法，一種是自底向上堆構造；另一種是自定向下堆構造。

自底向上構造

對于堆來說，每一個父母節點的值都要大于子女節點。所以從最后一個父母節點開始，一直到根節點，判斷子女節點是否比父母節點的值小，如果大，則將交換父母節點和子女節點的值。

以2算法分析中實現堆排序c語言程序，9，7，6，5，8為例：

自頂向下構造

自頂向下堆構造算法的效率低，就是通過把新的鍵連續插入預先構造好的堆，然后將其值與父母進行比較直至根節點或值小于父母節點時，來構造一個新堆。

比如在下面的堆中插入9：

關于最大堆，最小堆

最大堆就是父節點比子節點大，最小堆就是父母節點比子節點小。

堆排序 堆排序的一般過程

這里以

構造堆，堆給定的數組構造堆刪除最大鍵，將最大值和最后一個葉子結點進行交換，然后刪除將刪除后重新整合，使之成為一個堆，重復2 堆排序樣例過程圖解

以2，9，7，6，5，8為例

c語言代碼

#include 
int num;
void BuildHeap(int A[],int i,int N)	//構造堆  
{
	int c,temp;
    for (temp=A[i];2*i<=N;i=c)	//temp記錄下父母節點的值，c為一個子女節點 
	{
        c=2*i;				
        if(c<N&& A[c+1]>A[c])//找到最大的子女節點 
            ++c;              
        if(temp<A[c])		//父母節點值等于子女節點中大的 
            A[i]=A[c];		
        else
            break;					
    }
    A[i]=temp;//對被交換的子女節點賦值 比如在2 9 8 6 5 7中9和2交換后，2需要和6再進行交換，最后只需要對6最開始的位置賦值2就行 
}
void Heapsort(int a[])	//排序 
	{
		int i,temp;
		for(i=num/2;i>=1;i--)	//從最后一個父母節點開始，知道根節點 
			{
				BuildHeap(a,i,num);
			}
		for(i=num;i>0;i--)	//刪除根節點后，重新構造堆 
			{
				temp=a[1];
				a[1]=a[i];
				a[i]=temp;
				BuildHeap(a,1,i-1);
			}
	}
int main()
{
	printf("請輸入要排序的數的個數："); 
	scanf("%d",&num);
	int i,a[num+1];
	printf("請輸入元素：");
	for(i=1;i<=num;i++)
		scanf("%d",&a[i]);
	Heapsort(a);
	for(i=1;i<=num;i++)
		printf("%d ",a[i]);
 } 

參考書籍：算法設計與分析基礎