# 怎么实现堆排序？详细解析和代码实现

2021年3月31日13:24:36 发表评论 344 次浏览

## 本文概述

1. 根据输入数据构建最大堆。

2. 此时, 最大的项目存储在堆的根目录中。将其替换为堆的最后一项, 然后将堆的大小减小1。最后, 堆放树的根。

3. 堆大小大于1时, 请重复步骤2。

``````Input data: 4, 10, 3, 5, 1
4(0)
/   \
10(1)   3(2)
/   \
5(3)    1(4)

The numbers in bracket represent the indices in the array
representation of data.

Applying heapify procedure to index 1:
4(0)
/   \
10(1)    3(2)
/   \
5(3)    1(4)

Applying heapify procedure to index 0:
10(0)
/  \
5(1)  3(2)
/   \
4(3)    1(4)
The heapify procedure calls itself recursively to build heap
in top down manner.``````

## C++

``````// C++ program for implementation of Heap Sort
#include <iostream>

using namespace std;

// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify( int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2

// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;

// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;

// If largest is not root
if (largest != i)
{
swap(arr[i], arr[largest]);

// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}

// main function to do heap sort
void heapSort( int arr[], int n)
{
// Build heap (rearrange array)
for ( int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

// One by one extract an element from heap
for ( int i=n-1; i>0; i--)
{
// Move current root to end
swap(arr[0], arr[i]);

// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}

/* A utility function to print array of size n */
void printArray( int arr[], int n)
{
for ( int i=0; i<n; ++i)
cout << arr[i] << " " ;
cout << "\n" ;
}

// Driver program
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof (arr)/ sizeof (arr[0]);

heapSort(arr, n);

cout << "Sorted array is \n" ;
printArray(arr, n);
}``````

## Java

``````// Java program for implementation of Heap Sort
public class HeapSort
{
public void sort( int arr[])
{
int n = arr.length;

// Build heap (rearrange array)
for ( int i = n / 2 - 1 ; i >= 0 ; i--)
heapify(arr, n, i);

// One by one extract an element from heap
for ( int i=n- 1 ; i> 0 ; i--)
{
// Move current root to end
int temp = arr[ 0 ];
arr[ 0 ] = arr[i];
arr[i] = temp;

// call max heapify on the reduced heap
heapify(arr, i, 0 );
}
}

// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify( int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 *i + 1 ; // left = 2*i + 1
int r = 2 *i + 2 ; // right = 2*i + 2

// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;

// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;

// If largest is not root
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;

// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}

/* 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[] = { 12 , 11 , 13 , 5 , 6 , 7 };
int n = arr.length;

HeapSort ob = new HeapSort();
ob.sort(arr);

System.out.println( "Sorted array is" );
printArray(arr);
}
}``````

## python

``````# Python program for implementation of heap Sort

# To heapify subtree rooted at index i.
# n is size of heap
def heapify(arr, n, i):
largest = i # Initialize largest as root
l = 2 * i + 1     # left = 2*i + 1
r = 2 * i + 2     # right = 2*i + 2

# See if left child of root exists and is
# greater than root
if l < n and arr[i] < arr[l]:
largest = l

# See if right child of root exists and is
# greater than root
if r < n and arr[largest] < arr[r]:
largest = r

# Change root, if needed
if largest ! = i:
arr[i], arr[largest] = arr[largest], arr[i] # swap

# Heapify the root.
heapify(arr, n, largest)

# The main function to sort an array of given size
def heapSort(arr):
n = len (arr)

# Build a maxheap.
for i in range (n / / 2 - 1 , - 1 , - 1 ):
heapify(arr, n, i)

# One by one extract elements
for i in range (n - 1 , 0 , - 1 ):
arr[i], arr[ 0 ] = arr[ 0 ], arr[i] # swap
heapify(arr, i, 0 )

# Driver code to test above
arr = [ 12 , 11 , 13 , 5 , 6 , 7 ]
heapSort(arr)
n = len (arr)
print ( "Sorted array is" )
for i in range (n):
print ( "%d" % arr[i]), # This code is contributed by Mohit Kumra``````

## C#

``````// C# program for implementation of Heap Sort
using System;

public class HeapSort
{
public void sort( int [] arr)
{
int n = arr.Length;

// Build heap (rearrange array)
for ( int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

// One by one extract an element from heap
for ( int i=n-1; i>0; i--)
{
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;

// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}

// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify( int [] arr, int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2

// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;

// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;

// If largest is not root
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;

// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}

/* 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]+ " " );
}

// Driver program
public static void Main()
{
int [] arr = {12, 11, 13, 5, 6, 7};
int n = arr.Length;

HeapSort ob = new HeapSort();
ob.sort(arr);

Console.WriteLine( "Sorted array is" );
printArray(arr);
}
}

// This code is contributed
// by Akanksha Rai(Abby_akku)``````

## PHP

``````<?php

// Php program for implementation of Heap Sort

// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
function heapify(& \$arr , \$n , \$i )
{
\$largest = \$i ; // Initialize largest as root
\$l = 2* \$i + 1; // left = 2*i + 1
\$r = 2* \$i + 2; // right = 2*i + 2

// If left child is larger than root
if ( \$l < \$n && \$arr [ \$l ] > \$arr [ \$largest ])
\$largest = \$l ;

// If right child is larger than largest so far
if ( \$r < \$n && \$arr [ \$r ] > \$arr [ \$largest ])
\$largest = \$r ;

// If largest is not root
if ( \$largest != \$i )
{
\$swap = \$arr [ \$i ];
\$arr [ \$i ] = \$arr [ \$largest ];
\$arr [ \$largest ] = \$swap ;

// Recursively heapify the affected sub-tree
heapify( \$arr , \$n , \$largest );
}
}

// main function to do heap sort
function heapSort(& \$arr , \$n )
{
// Build heap (rearrange array)
for ( \$i = \$n / 2 - 1; \$i >= 0; \$i --)
heapify( \$arr , \$n , \$i );

// One by one extract an element from heap
for ( \$i = \$n -1; \$i > 0; \$i --)
{
// Move current root to end
\$temp = \$arr [0];
\$arr [0] = \$arr [ \$i ];
\$arr [ \$i ] = \$temp ;

// call max heapify on the reduced heap
heapify( \$arr , \$i , 0);
}
}

/* A utility function to print array of size n */
function printArray(& \$arr , \$n )
{
for ( \$i = 0; \$i < \$n ; ++ \$i )
echo ( \$arr [ \$i ]. " " ) ;

}

// Driver program
\$arr = array (12, 11, 13, 5, 6, 7);
\$n = sizeof( \$arr )/sizeof( \$arr [0]);

heapSort( \$arr , \$n );

echo 'Sorted array is ' . "\n" ;

printArray( \$arr , \$n );

// This code is contributed by Shivi_Aggarwal
?>``````

``````Sorted array is
5 6 7 11 12 13``````

HeapSort的应用

1.对几乎排序(或K排序)的数组进行排序

2.数组中的k个最大(或最小)元素