图说 堆排序,堆排序

图说 堆排序,堆排序

 用例:

将一组数据从大到小进行排列  10, 16, 18, 12, 11, 13, 15, 17, 14, 19  

   size=10

 步骤1.根据数组初始化堆

图片 1

 

步骤2.从最后一个根节点( 下标为(size-1-1)/2
)开始往第一个根节点遍历,依次将每个最小子树排好序,建造一个小堆:图片 2图片 3

 步骤3.进行堆排序:将堆数组的首位置和末位置的数据交换,缩小范围 以–size大小的范围将堆顶数据下调,完成建堆

 图片 4

 

图片 5

 图片 6图片 7图片 8图片 9图片 10图片 11图片 12图片 13

理解了整个思想,我们就来看代码:
先实现一个下调函数用来建堆,并对堆进行调整:(本案例是从大到小进行排序,所以建的是小堆;若是要从小到大进行排序,则要按照大堆思想进行实现,对代码稍微进行改进即可)

//下调
void AdjustDown(int *array, int parent, int size) 
{
 int left = parent * 2 + 1;
 int right = left + 1;
 while (left < size)
 {
  // 比较左右孩子,保证下标left为最小的节点下标
  if (right <size && array[right] < array[left])
  {
   left = right;
  }
  // 如果父节点大于左右孩子中较小的节点时,就交换这两个节点,要保证两个子节点都大于父节点
  if (left<size && array[parent]>array[left])
  {
   // 交换之后还需继续 将相对较大的数循环向下调
   swap(array[left], array[parent]);
   parent = left;
   left = parent * 2 + 1;
   right = left + 1;
  }
  else
  {
   break;
  }
 }
}

  堆排序:按照图说的步骤来写代码,首先要初始化一个堆数组并对它进行排序,之后再一步步将堆顶与有效堆尾数据进行交换,并逐渐缩小堆的size,一组有序的数据就排好了!

//堆排序
int* HeapSort(int *heap, int size)
{
 for (int start = (size - 1 - 1) / 2; start >= 0; start--)
 {
  AdjustDown(heap, start, size);
 }
 for (int i = size - 1; i >= 0; --i)
 {
  swap(heap[0], heap[i]);
  AdjustDown(heap, 0, i);
 }
 return heap;
}

  

 

堆排序,堆排序 用例: 将一组数据 从大到小
进行排列10, 16, 18, 12, 11, 13, 15, 17, 14, 19 size=10
步骤1.根据数组初始化堆 步骤2.从最后一个…

初始时候,堆排序算法利用BUILD-MAX-HEAP将输入数组A[1..n]建成最大堆,其中n=A.length。因为数组中的最大元素总在根结点A[1]中,通过把它与A[n]进行互换,我们可以让该元素放到正确的位置。这时候,如果我们从堆中去掉结点n(这一操作可以通过减少A.heap-size的值的实现),剩余的结点中,原来根的孩子结点仍然是最大堆,而新的根结点可能会违背最大堆的性质。为了维护最大堆的性质,我们要做的是调用MAX-HEAPIFY(A,
1),从而在A[1..n-1]上构造一个新的最大堆。堆排序算法会不断重复这一过程,直到堆的大小从n-1降到2。(准确的循环不变量定义见练习6.4-2。)

堆排序,堆排序复杂度

堆排序是基于二叉树。n个关键字序列Kl,K2,…,Kn称为(Heap),当且仅当该序列满足如下性质(简称为堆性质):

(1)ki<=k(2i)且ki<=k(2i+1)(1≤i≤
n/2),当然,这是小根堆,大根堆则换成>=号。//k(i)相当于二叉树的非叶子结点,K(2i)则是左子节点,k(2i+1)是右子节点。

堆排序的几个关键点:

1、一个节点的两个子节点已经是有序堆,调整这个节点为有序堆(递归调整);

2、创建堆:调整第一个非叶节点为有序堆,逐级向上,直到整个数组为有序堆。

3、堆顶与最后一个叶子节点调换,堆变小,再调整堆,再调换,直到堆大小为1,排序完成。

附上代码:

#include "stdafx.h"
#include <stdio.h>

/*
 * L     初始无序堆
 * n     节点序号
 * size  无序堆节点个数
 */
void Heapify(int L[], int n, int size)
{
    int rchild=2*n+1;
    int lchild=2*n;
    if (rchild<=size)
    {
        int max=L[lchild]>L[rchild] ? lchild : rchild;
        if (L[n]<L[max])
        {
            int temp=L[n];
            L[n]=L[max];
            L[max]=temp;
            Heapify(L,max,size);
        }
    }
    else if (lchild==size)
    {
        if (L[n]<L[lchild])
        {
            int temp=L[n];
            L[n]=L[lchild];
            L[lchild]=temp;
        }
    }
}

// 建堆(大根堆)
void BuildHeap(int L[], int size)
{
    for (int i=size/2; i>0; i--) // 从最低层的节点开始创建有序堆,直到整个堆是有序堆。
    {
        Heapify(L,i,size);
    }
}

// L[0]是暂存区
void HeapSort(int L[], int size)
{
    BuildHeap(L,size);
    for (int i=size; i>0; i--)
    {
        L[0]=L[1];
        L[1]=L[i];
        L[i]=L[0];
        Heapify(L,1,i-1);
    }
}

int main(int argc, char* argv[])
{
    // 待排序数据不包括L[0]
    int L[13]={5,1,7,2,90,6,-5,23,10,4,50,12,5};
    int i=0;
    for (i=1; i<13; i++)
    {
        printf("%5d",L[i]);
    }
    printf("\n");

    HeapSort(L,12);

    for (i=1; i<13; i++)
    {
        printf("%5d",L[i]);
    }
    printf("\n");

    return 0;
}

 

堆排序是基于二叉树。n个关键字序列Kl,K2,,Kn称为(Heap),当且仅当该序列满足如下性质(简称为堆性质):…

堆排序,堆排序算法

 1 #include<iostream>
 2 using namespace std;
 3 int heap[101];
 4 int heap_size;
 5 void put(int d)                 //heap[1]为堆顶   插入 
 6 {
 7     int now, next;
 8     heap[++heap_size] = d;
 9     now = heap_size;
10     while(now > 1)
11     {
12         next = now/2;// 父节点 
13         if(heap[now] >= heap[next]) 
14         break;
15         swap(heap[now], heap[next]);
16         now = next;
17     }
18 }
19 int get()                //heap[1]为堆顶  获取 
20 {
21     int now=1, next, res= heap[1];
22     heap[1] = heap[heap_size--];//取出末尾元素 
23     while(now * 2 <= heap_size)
24     {
25         next = now * 2;// next 左孩子 
26         if (next < heap_size && heap[next + 1] < heap[next])
27         next++;
28         if (heap[now] <= heap[next]) 
29         break;
30         swap(heap[now], heap[next]);
31         now = next;
32     }
33     return res;
34 }
35 
36 int main()
37 {
38     int n;
39     cin>>n;
40     for(int i=1;i<=n;i++)
41     {
42         int dr;
43         cin>>dr;
44         put(dr);
45     }
46     for(int i=1;i<=n;i++)
47     {
48         cout<<get()<<endl;
49     }
50     return 0;
51 }

 stl

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 using namespace std;
 5 int a[10000001];
 6 int main()
 7 {
 8     int n;
 9     cin>>n;
10     for(int i=1;i<=n;i++)
11     {
12         //cin>>a[i];
13         scanf("%d",&a[i]);
14     }
15     make_heap(a+1,a+n+1);
16     sort_heap(a+1,a+n+1);
17     for(int i=1;i<=n;i++)
18     {
19         //cout<<a[i]<<endl;
20         printf("%d\n",a[i]);
21     }
22     return 0;
23 } 

 

1 #includeiostream 2 using
namespace std; 3 int heap[ 101 ]; 4 int heap_size; 5 void put( int d)
// heap[1]为堆顶 插入 6 { 7 int now, next; 8 heap[…

图片 14

图6-4给出了一个在HEAPSORT的第1行建立初始最大堆之后,堆排序操作的一个例子。图6-4显示了第2~5行for循环第一次迭代开始前最大堆的情况和每一次迭代之后最大堆的情况。
HEAPSORT过程的时间复杂度是O(nlgn),因为每次调用BUILD-MAX-HEAP的时间复杂度是O(n),而n-1次调用MAX-HEAPIFY,每次的时间为O(lgn)。

图片 15

图6-4
HEAPSORT的运行过程。(a)执行堆排序算法第1行,用BUILD-MAX-HEAP构造得到的最大堆。(b)~(j)每次执行算法第5行,调用MAX-HEAPIFY后得到的最大堆,并标识当次的i值。其中,仅仅浅色阴影的结点被保留在堆中。(k)最终数组A的排序结果

练习
6.4-1 参照图6-4的方法,说明HEAPSORT在数组A=<5, 13, 2, 25, 7, 17, 20,
8, 4>上的操作过程。
6.4-2 试分析在使用下列循环不变量时,HEAPSORT的正确性:
在算法的第2~5行for循环每次迭代开始时,子数组A[1..i]是一个包含了数组A[1..n]中第i小元素的最大堆,而子数组A[i+1..n]包含了数组A[1..n]中已排序的n-i个最大元素?
6.4-3
对于一个按升序排列的包含n个元素的有序数组A来说,HEAPSORT的时间复杂度是多少?如果A是降序呢?
6.4-4 证明:在最坏情况下,HEAPSORT的时间复杂度是OMEGA(nlgn)。
*6.4-5
证明:在所有元素都不同的情况下,HEAPSORT的时间复杂度是OMEGA(nlgn)。

相关文章