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

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

## 本文概述

``````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``````

20 17 15 10 9 21

20 17 21 10 9 15

21 17 20 10 9 15

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

## 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``````

• A+