迭代堆排序解析和详细实现介绍

2021年3月9日15:58:40 发表评论 814 次浏览

本文概述

堆排序是一种基于比较的排序技术, 在此技术中, 我们首先构建Max Heap, 然后将根元素与最后一个元素(大小倍)交换, 并每次都维护heap属性以最终对其进行排序。

例子：

Input :  10 20 15 17 9 21
Output : 9 10 15 17 20 21 

Input:  12 11 13 5 6 7 15 5 19
Output: 5 5 6 7 11 12 13 15 19

在第一个示例中, 首先我们必须构建Max Heap。

因此, 我们将从20岁开始为孩子, 然后检查其父级。这里10较小, 因此我们将交换这两个。

现在, 20 10 15 17 9 21

现在, 子项17大于其父项10。因此, 两个子项都将被交换且顺序为

20 17 15 10 9 21

现在, 子级21大于父级15。因此, 两者都将交换。

20 17 21 10 9 15

现在, 21又比父级20大。

21 17 20 10 9 15

这是最大堆。

现在, 我们必须应用排序。在这里, 我们必须将第一个元素与最后一个元素交换, 并且必须维护Max Heap属性。

因此, 在第一次交换后：15 17 20 10 9 21

它显然违反了Max Heap属性。因此, 我们必须维护它。因此, 订单将

20 17 15 10 9

21

17 10 15 9

20 21

15 10 9

17 20 21

10 9

15 17 20 21

9 10 15 17 20 21

在此, 带下划线的部分是排序的部分。

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

C ++

// C++ program for implementation 
// of Iterative Heap Sort
#include <bits/stdc++.h>
using namespace std;
  
// function build Max Heap where value 
// of each child is always smaller
// than value of their parent
void buildMaxHeap( int arr[], int n) 
{ 
     for ( int i = 1; i < n; i++) 
     {
         // if child is bigger than parent
         if (arr[i] > arr[(i - 1) / 2]) 
         {
             int j = i;
      
             // swap child and parent until
             // parent is smaller
             while (arr[j] > arr[(j - 1) / 2]) 
             {
                 swap(arr[j], arr[(j - 1) / 2]);
                 j = (j - 1) / 2;
             }
         }
     }
}
  
void heapSort( int arr[], int n) 
{
     buildMaxHeap(arr, n);
  
     for ( int i = n - 1; i > 0; i--)
     {
         // swap value of first indexed 
         // with last indexed 
         swap(arr[0], arr[i]);
      
         // maintaining heap property
         // after each swapping
         int j = 0, index;
          
         do
         {
             index = (2 * j + 1);
              
             // if left child is smaller than 
             // right child point index variable 
             // to right child
             if (arr[index] < arr[index + 1] &&
                                 index < (i - 1))
                 index++;
          
             // if parent is smaller than child 
             // then swapping parent with child 
             // having higher value
             if (arr[j] < arr[index] && index < i)
                 swap(arr[j], arr[index]);
          
             j = index;
          
         } while (index < i);
     }
}
  
// Driver Code to test above
int main() 
{
     int arr[] = {10, 20, 15, 17, 9, 21};
     int n = sizeof (arr) / sizeof (arr[0]);
      
     printf ( "Given array: " );
     for ( int i = 0; i < n; i++)
         printf ( "%d " , arr[i]);
          
     printf ( "\n\n" ); 
  
     heapSort(arr, n);
  
     // print array after sorting
     printf ( "Sorted array: " );
     for ( int i = 0; i < n; i++)
         printf ( "%d " , arr[i]);
  
     return 0;
}

Java

// Java implementation of Iterative Heap Sort 
public class HeapSort {
  
   // function build Max Heap where value
   // of each child is always smaller
   // than value of their parent
   static void buildMaxHeap( int arr[], int n)
   {
     for ( int i = 1 ; i < n; i++)
     {
       // if child is bigger than parent
       if (arr[i] > arr[(i - 1 ) / 2 ])
       {
         int j = i;
  
         // swap child and parent until
         // parent is smaller
         while (arr[j] > arr[(j - 1 ) / 2 ])
         {
           swap(arr, j, (j - 1 ) / 2 );
           j = (j - 1 ) / 2 ;
         }
       }
     }
   }
  
   static void heapSort( int arr[], int n)
   {
     buildMaxHeap(arr, n);
  
     for ( int i = n - 1 ; i > 0 ; i--)
     {
       // swap value of first indexed
       // with last indexed
       swap(arr, 0 , i);
  
       // maintaining heap property
       // after each swapping
       int j = 0 , index;
  
       do
       {
         index = ( 2 * j + 1 );
  
         // if left child is smaller than
         // right child point index variable
         // to right child
         if (index < (i - 1 ) && arr[index] < arr[index + 1 ])
           index++;
  
         // if parent is smaller than child
         // then swapping parent with child
         // having higher value
         if (index < i && arr[j] < arr[index])
           swap(arr, j, index);
  
         j = index;
  
       } while (index < i);
     }
   }
  
   public static void swap( int [] a, int i, int j) {
     int temp = a[i];
     a[i]=a[j];
     a[j] = temp;
   }
  
   /* A utility function to print array of size n */
   static void printArray( int arr[])
   {
     int n = arr.length;
     for ( int i = 0 ; i < n; i++)
       System.out.print(arr[i] + " " );
     System.out.println();
   }
  
   // Driver program
   public static void main(String args[])
   {
     int arr[] = { 10 , 20 , 15 , 17 , 9 , 21 };
     int n = arr.length;
  
     System.out.print( "Given array: " );
     printArray(arr);
  
     heapSort(arr, n);
  
     System.out.print( "Sorted array: " );
     printArray(arr);
   }
}

Python3

# Python3 program for implementation 
# of Iterative Heap Sort 
  
# function build Max Heap where value 
# of each child is always smaller 
# than value of their parent 
def buildMaxHeap(arr, n): 
  
     for i in range (n):
          
         # if child is bigger than parent 
         if arr[i] > arr[ int ((i - 1 ) / 2 )]:
             j = i 
      
             # swap child and parent until 
             # parent is smaller 
             while arr[j] > arr[ int ((j - 1 ) / 2 )]:
                 (arr[j], arr[ int ((j - 1 ) / 2 )]) = (arr[ int ((j - 1 ) / 2 )], arr[j])
                 j = int ((j - 1 ) / 2 )
  
def heapSort(arr, n): 
  
     buildMaxHeap(arr, n) 
  
     for i in range (n - 1 , 0 , - 1 ):
          
         # swap value of first indexed 
         # with last indexed 
         arr[ 0 ], arr[i] = arr[i], arr[ 0 ]
      
         # maintaining heap property 
         # after each swapping 
         j, index = 0 , 0
          
         while True :
             index = 2 * j + 1
              
             # if left child is smaller than 
             # right child point index variable 
             # to right child 
             if (index < (i - 1 ) and 
                 arr[index] < arr[index + 1 ]): 
                 index + = 1
          
             # if parent is smaller than child 
             # then swapping parent with child 
             # having higher value 
             if index < i and arr[j] < arr[index]: 
                 arr[j], arr[index] = arr[index], arr[j] 
          
             j = index 
             if index > = i:
                 break
  
# Driver Code
if __name__ = = '__main__' :
     arr = [ 10 , 20 , 15 , 17 , 9 , 21 ] 
     n = len (arr) 
      
     print ( "Given array: " )
     for i in range (n):
         print (arr[i], end = " " ) 
          
     print () 
  
     heapSort(arr, n) 
  
     # print array after sorting 
     print ( "Sorted array: " )
     for i in range (n):
         print (arr[i], end = " " )
  
# This code is contributed by PranchalK

C#

// C# implementation of Iterative Heap Sort 
using System;
      
class HeapSort 
{
  
// function build Max Heap where value
// of each child is always smaller
// than value of their parent
static void buildMaxHeap( int []arr, int n)
{
     for ( int i = 1; i < n; i++)
     {
         // if child is bigger than parent
         if (arr[i] > arr[(i - 1) / 2])
         {
             int j = i;
      
             // swap child and parent until
             // parent is smaller
             while (arr[j] > arr[(j - 1) / 2])
             {
                 swap(arr, j, (j - 1) / 2);
                 j = (j - 1) / 2;
             }
         }
     }
}
  
static void heapSort( int []arr, int n)
{
     buildMaxHeap(arr, n);
  
     for ( int i = n - 1; i > 0; i--)
     {
          
         // swap value of first indexed
         // with last indexed
         swap(arr, 0, i);
      
         // maintaining heap property
         // after each swapping
         int j = 0, index;
      
         do
         {
             index = (2 * j + 1);
      
             // if left child is smaller than
             // right child point index variable
             // to right child
             if (index < (i - 1) && arr[index] < 
                                    arr[index + 1])
             index++;
      
             // if parent is smaller than child
             // then swapping parent with child
             // having higher value
             if (index < i && arr[j] < arr[index])
                 swap(arr, j, index);
      
             j = index;
      
         } while (index < i);
     }
}
  
public static void swap( int [] a, int i, int j) 
{
     int temp = a[i];
     a[i] = a[j];
     a[j] = temp;
}
  
/* A utility function to print array of size n */
static void printArray( int []arr)
{
     int n = arr.Length;
     for ( int i = 0; i < n; i++)
     Console.Write(arr[i] + " " );
     Console.WriteLine();
}
  
// Driver Code
public static void Main(String []args)
{
     int []arr = {10, 20, 15, 17, 9, 21};
     int n = arr.Length;
  
     Console.Write( "Given array: " );
     printArray(arr);
  
     heapSort(arr, n);
  
     Console.Write( "Sorted array: " );
     printArray(arr);
}
}
  
// This code is contributed by Princi Singh

输出：

Given array: 10 20 15 17 9 21 

Sorted array: 9 10 15 17 20 21

在这里, buildMaxHeap和heapSort函数都在O(nlogn)时间运行。因此, 整体时间复杂度为O(nlogn)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: