Implementation of heap sort for internal sort

2020-04-01 23:44:12
OfStack

Heap Sort requires only an auxiliary space of record size, and each record to be sorted occupies only one storage space.
(1) basic concepts
A) heap: a sequence with n elements:
{k1, k2,... , kn}
For all I =1,2... ,(int)(n/2), when the following relation is satisfied:
Ki k2i or less, ki k2i + 1 or less
or Ki acuity k2i, ki k2i + 1 or more
Such a sequence is called a heap.
There are two types of heap:
The smallest heap at the root - a small root heap.
The largest heap at the root - the large root heap.
The root node is called the top of the heap, that is, in a complete binary tree, the value of all non-leaves is less than (or greater than) the value of left and right children.
B) heap sort: it is a kind of tree selection sort. In the process of sorting, R[1..
2) heap sort steps:
1. Starting from the right-most non-leaf node of k-1 layer, make the record with large (or small) keyword value move to the upper layer of the binary tree step by step, and make the record with the largest (or small) keyword become the root node of the tree and become the heap.
2, gradually output the root node, let r[1]=r[I](I =n, n-1,... ,2), and then pile up the remaining nodes. All the way to the output. We call this process of adjustment from the top of the stack to the leaves "sifting."
(3) two problems to be solved:
1. How to build a heap from an unordered sequence;
2, after the output of a root node, how to adjust the remaining elements into a heap.
Building an unordered sequence into a heap is a process of repeated "filtering". If you view this sequence as a complete binary tree, then the last non-terminal node is the first floor(n/2) elements, so the "filter" simply starts with the first floor(n/2) elements.
A secondary space of record size is required in heap sort, and each record to be queued occupies only one storage space. Heap sort is not recommended when records are low. When n is large, it's efficient. Heap sort is unstable.
The heapsort algorithm and the filter algorithm are shown in section 2. Orderly arrangement to make the sorting result is decreasing, we in the sorting algorithm to build a "big heap", namely the first choose a keyword for the greatest record and with the last record in the sequence, then the sequence of the top n - 1 filtered records, to adjust it to a "big heap", and then choose to a keyword for the greatest record (that is, the first element) and the current last record exchange (global look at is the first n - 1), so on, until the end of the sort. From to, the filtering should be carried out downward by the child node with the larger keyword.
The algorithm description of heap sort is as follows: < img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201305/201305241448328.gif ">

< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201305/201305241448329.gif ">

< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201305/2013052414483210.gif ">

The C language code is as follows:


#include "iostream"
using namespace std;
#define MAXSIZE 20
typedef struct
{
 int key;
 //Other data information
}RedType;
typedef struct
{
 RedType r[MAXSIZE+1];
 int length;
}Sqlist;
typedef Sqlist HeapType;  //The heap is represented by a sequential table of storage
void HeapAdjust(HeapType &H,int s,int m)   //It is known that all the keywords recorded in H.r[s...m] meet the definition of heap except H.r[s]. This function adjusts the keyword of H.r[s] to make H.r[s...m] become a big top heap (for the keywords recorded in it).
{
 int j;
 RedType rc;
 rc=H.r[s];
 for(j=2*s;j<=m;j*=2)   //Filter down the child node with the larger key
 {
  if(j<m && (H.r[j].key<H.r[j+1].key))     //J is the subscript of a record with a larger key
   ++j;
  if(rc.key>=H.r[j].key)           //Rc should be inserted at position s
   break;
  H.r[s]=H.r[j];      //The larger node of left and right children is exchanged with the parent node to build a big top pile
  s=j;
 }
 H.r[s]=rc;             //insert
}
void HeapSort(HeapType &H)      //Heap sort the order table H
{
 int i;
 for(i=H.length/2;i>0;--i)   //A large top heap is constructed from an unordered sequence, which is regarded as a complete binary tree, and the last non-terminal node is the NTH / 2nd element
  HeapAdjust(H,i,H.length);
 for(i=H.length;i>1;--i)
 {
  H.r[0]=H.r[1];   //Swap the heap top record with the last record in the currently unsorted sequence H.r[1... I]
  H.r[1]=H.r[i];
  H.r[i]=H.r[0];
  HeapAdjust(H,1,i-1);    //Reset H.r[1...i-1] to large top heap
 }
}//HeapSort
void InputL(Sqlist &L)
{
 int i;
 printf("Please input the length:");
 scanf("%d",&L.length);
 printf("Please input the data needed to sort:n");
 for(i=1;i<=L.length;i++)    //The first index of the array is stored, and the 0th index is used as a temporary variable for exchange
  scanf("%d",&L.r[i].key);
}
void OutputL(Sqlist &L)
{
 int i;
 printf("The data after sorting is:n");
 for(i=1;i<=L.length;i++)
  printf("%d ",L.r[i].key);
 printf("n");
}
int main(void)
{
 Sqlist H;
 InputL(H);
 HeapSort(H);
 OutputL(H);
 system("pause");
 return 0;
}

Another way to not use the above structure is as follows:



#include "iostream"
using namespace std;
#define N 10
int array[N];
void man_input(int *array)
{
 int i;
 for(i=1;i<=N;i++)
 {
  printf("array[%d]=",i);
  scanf("%d",&array[i]);
 }
}
void mySwap(int *a,int *b)//exchange
{
 int temp;
 temp=*a;
 *a=*b;
 *b=temp;
}
void heap_adjust(int *heap,int root,int len)     //The heap is adjusted so that the unordered sequence of subscripts from root to len becomes a large top heap
{
 int i=2*root;
 int t=heap[root];
 while(i<=len)
 {
  if(i<len)
  {
   if(heap[i]<heap[i+1])
    i++;
  }
  if(t>=heap[i])
   break;
  heap[i/2]=heap[i];
  i=2*i;
 }
 heap[i/2]=t;
}
void heapSort(int *heap,int len)      //Heap sort
{
 int i;
 for(i=len/2;i>0;i--)    //A large top heap is constructed from an unordered sequence, which is regarded as a complete binary tree, and the last non-terminal node is the len/2 element
 {
  heap_adjust(heap,i,len);
 }
 for(i=len;i>=1;i--)
 {
  mySwap(heap+i,heap+1);    // Cross the heap top record with the last record exchange
  heap_adjust(heap,1,i-1);   //Readjust the records subscript 1 to I -1 to the large top heap
 }
}
void print_array(int *array,int n)
{
 int k;
 for(k=1;k<n+1;k++)
 {
  printf("%dt",array[k]);
 }
}
int main(void)
{
 man_input(array);
 heapSort(array,N);
 printf("nAfter sorted by the heap_sort algorithm:n");        
 print_array(array,N);   // print Heap sort The results of 
 system("pause");
 return 0;
}