迭代堆排序解析和详细实现介绍 _数据结构

本文概述

建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
C ++
Java
Python3
C#

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

Input :10 20 15 17 9 21Output : 9 10 15 17 20 21 Input:12 11 13 5 6 7 15 5 19Output: 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 , 0while 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# 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

输出：