Heapsort是一种使用二进制堆进行排序的排序算法。
堆可以有两种类型，最小堆和最大堆。

Heapsort是选择排序的改进版本。

在本教程中，我们将使用最大堆来实现Heapsort。

最大堆遵循父元素始终大于其子元素的属性。
这意味着在最大堆中，根始终是所有元素的最大值。
Heapsort使用此属性以排序的方式排列元素。

算法

Heapsort的算法如下：

• 从输入数组构建最大堆。

• 将root(最大值)替换为堆的最后一项。

• 将堆大小减小1。

• 通过调用DownHeapify来堆满树的根

• 当堆的大小大于1时，请重复步骤2至4。

在每次迭代中，我们采用最大元素并将其放在堆的末尾。
然后我们减小堆的大小。
在进行此过程时，我们将从最后开始对数组进行排序。

我们将调用函数downheapify()来确保在减小大小后满足了heap属性。

堆排序实现

为了堆积数组，我们使用了一个从根到叶节点的递归函数。
每个节点上的此功能都会将父级与其子级进行比较。
如果父节点的值小于其子节点的值，它将交换值。
此交换可确保满足最大堆属性。

执行交换后，如果进一步调用子代上的downheapify函数。

每次在堆中添加或者删除元素时都需要调用此函数。

在堆中，孩子的位置由下式给出：

Left child : (2*i) + 1
Right child : (2*i) + 2 

downheapify的代码如下：

static void downheapify(int arr[], int n, int i)
  {
      int largest = i;
      int l = 2*i + 1;
      int r = 2*i + 2;

      //finding the maximum of left and right
      if (l < n && arr[l] > arr[largest])
          largest = l;

      if (r < n && arr[r] > arr[largest])
          largest = r;

      //swapping if child >parent
      if (largest != i)
      {
          int swap = arr[i];
          arr[i] = arr[largest];
          arr[largest] = swap;

          downheapify(arr, n, largest);
      }
  }

要对数组排序，我们首先需要从中创建一个堆。
这是通过以下代码行完成的：

for (int i = n/2 - 1; i >= 0; i--)
          downheapify(arr, n, i);

我们只需要在调用downheapify时考虑非叶子节点，因为叶子节点已经满足了heap属性。

下一步是从根位置提取元素，然后将其与堆的最后位置交换。
完成此操作后，我们将减小堆的大小，然后再次调用downheapify。
执行此操作的代码行是：

for (int i=n-1; i>0; i--)
      {
        //swap the last element with root
          int temp = arr[0];
          arr[0] = arr[i];
          arr[i] = temp;

        //i is the size of the reduced heap
         downheapify(arr, i, 0);
      }

排序功能的完整代码为：

public static void sort(int arr[])
  {
      int n = arr.length;

    //build heap by calling heapify on non leaf elements
      for (int i = n/2 - 1; i >= 0; i--)
          downheapify(arr, n, i);

   //extract elements from the root and call healpify
      for (int i=n-1; i>0; i--)
      {
        //swap the last element with root
          int temp = arr[0];
          arr[0] = arr[i];
          arr[i] = temp;

          //i is the size of the reduced heap
          downheapify(arr, i, 0);
      }
  }

除了这两个函数外，我们还需要一个函数来打印数组。

打印功能如下：

static void printArray(int arr[])
  {
      int n = arr.length;
      for (int i=0; i<n; ++i)
          System.out.print(arr[i]+" ");
      System.out.println();
  }

使用这三个功能，我们可以成功实现Heapsort。

完整的代码

Heapsort的完整代码如下：

1. Java中的堆排序

package com.theitroad;

public class Main {
  static void downheapify(int arr[], int n, int i)
  {
      int largest = i;
      int l = 2*i + 1;
      int r = 2*i + 2;

      //finding the maximum of left and right
      if (l < n && arr[l] > arr[largest])
          largest = l;

      if (r < n && arr[r] > arr[largest])
          largest = r;

      //swapping if child >parent
      if (largest != i)
      {
          int swap = arr[i];
          arr[i] = arr[largest];
          arr[largest] = swap;

          downheapify(arr, n, largest);
      }
  }

  public static void sort(int arr[])
  {
      int n = arr.length;

    //build heap by calling heapify on non leaf elements
      for (int i = n/2 - 1; i >= 0; i--)
          downheapify(arr, n, i);

   //extract elements from the root and call healpify
      for (int i=n-1; i>0; i--)
      {
        //swap the last element with root
          int temp = arr[0];
          arr[0] = arr[i];
          arr[i] = temp;

          //i is the size of the reduced heap
          downheapify(arr, i, 0);
      }
  }
  static void printArray(int arr[])
  {
      int n = arr.length;
      for (int i=0; i<n; ++i)
          System.out.print(arr[i]+" ");
      System.out.println();
  }
  public static void main(String[] arg)
  {
      int arr[] = {1, 10, 2, 3, 4, 1, 2, 100,23, 2};
      int n = arr.length;
      sort(arr);
      System.out.println("Sorted array is");
      printArray(arr);

  }

}

2. C++中的堆排序

#include <iostream> 

using namespace std; 

void downheapify(int arr[], int n, int i) 
{ 
  int largest = i; 
  int l = 2*i + 1; 
  int r = 2*i + 2; 

  if (l < n && arr[l] > arr[largest]) 
      largest = l; 

  if (r < n && arr[r] > arr[largest]) 
      largest = r; 
 
  if (largest != i) 
  { 
       swap(arr[i], arr[largest]);           downheapify(arr, n, largest); 
  } 
} 

void heapSort(int arr[], int n) 
{ 
  
  for (int i = n/2 - 1; i >= 0; i--) 
      heapify(arr, n, i); 

  
  for (int i=n-1; i>0; i--) 
  { 
     
      swap(arr[0], arr[i]); 

      heapify(arr, i, 0); 
  } 
} 
 
void printArray(int arr[], int n) 
{ 
  for (int i=0; i<n; ++i) 
      cout << arr[i] << " "; 
  cout << "\n"; 
} 

int main() 
{ 
 int arr[] = {1, 10, 2, 3, 4, 1, 2, 100,23, 2}; 
  int n = sizeof(arr)/sizeof(arr[0]); 

  heapSort(arr, n); 

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

Output : 

Sorted array is
1 1 2 2 2 3 4 10 23 100