设计与分析——堆排序

堆排序是一种基于堆排序的高效排序技术>堆数据结构。

堆是一个近乎完整的二叉树，其中父节点可以是最小的也可以是最大的。具有最小根节点的堆称为最小堆，具有最大根节点的堆称为最大堆。堆排序算法的输入数据中的元素使用这两种方法进行处理。

堆排序算法在此过程中遵循两个主要操作 -

  • 根据排序方式（升序或降序），使用heapify （本章将进一步解释）方法从输入数据构建堆 H。

  • 删除根元素的根元素并重复，直到处理完所有输入元素。

堆排序算法

堆排序算法很大程度上依赖于二叉树的heapify方法。那么这个heapify方法是什么呢？

堆化法

二叉树的heapify方法就是将二叉树转换为堆数据结构。该方法使用递归方法来堆化二叉树的所有节点。

注意- 二叉树必须始终是完全二叉树，因为它必须始终有两个子节点。

通过应用heapify方法，完整的二叉树将转换为最大堆或最小堆。

要了解有关 heapify 算法的更多信息，请单击此处。

堆排序算法

正如下面的算法所述，排序算法首先通过调用Build-Max-Heap算法构造堆ADT，并删除根元素以将其与叶子处的最小值节点交换。然后应用 heapify 方法相应地重新排列元素。

Algorithm: Heapsort(A)
BUILD-MAX-HEAP(A)
for i = A.length downto 2
exchange A[1] with A[i]
A.heap-size = A.heap-size - 1
MAX-HEAPIFY(A, 1)

分析

堆排序算法是另外两种排序算法的组合：插入排序和归并排序。

与插入排序的相似之处在于，任何时候只有恒定数量的数组元素存储在输入数组之外。

堆排序算法的时间复杂度为O(nlogn)，类似于归并排序。

例子

让我们看一个示例数组以更好地理解排序算法 -

12 3 9 14 10 18 8 23

使用 BUILD-MAX-HEAP 算法从输入数组构建堆 -

构建最大堆

通过交换节点重新排列得到的二叉树，形成堆数据结构。

堆数据结构 23_至_3 23_至_12 14_至_3 14_至_12 18_to_9.jpg

堆排序算法

应用 heapify 方法，从堆中删除根节点，并将其替换为根的下一个直接最大值子节点。

根节点是 23，因此 23 被弹出，18 成为下一个根，因为它是堆中的下一个最大节点。

23_弹出

现在，18 在 23 之后被弹出，被 14 取代。

18_弹出

当前根 14 从堆中弹出并替换为 12。

14_弹出

12 被弹出并替换为 10。

12_弹出

类似地，所有其他元素都使用相同的过程弹出。

10_弹出 9_弹出 8_popped.jpg all_element_popped.jpg

每次弹出一个元素时，它都会添加到输出数组的开头，因为形成的堆数据结构是最大堆。但如果 heapify 方法将二叉树转换为最小堆，则将弹出的元素添加到输出数组的末尾。

最终的排序列表是，

3 8 9 10 12 14 18 23

执行

堆排序的实现逻辑是：首先，根据 max-heap 属性构建堆数据结构，其中父节点的值必须大于子节点的值。然后从堆中弹出根节点，并将堆上的下一个最大节点移动到根。该过程不断迭代，直到堆为空。

在本教程中，我们展示了四种不同编程语言的堆排序实现。

C C++ Java Python 
#include <stdio.h>
void heapify(int[], int);
void build_maxheap(int heap[], int n){
   int i, j, c, r, t;
   for (i = 1; i < n; i++) {
      c = i;
      do {
         r = (c - 1) / 2;
         if (heap[r] < heap[c]) { // to create MAX heap array
            t = heap[r];
            heap[r] = heap[c];
            heap[c] = t;
         }
         c = r;
      } while (c != 0);
   }
   printf("Heap array: ");
   for (i = 0; i < n; i++)
      printf("%d ", heap[i]);
   heapify(heap, n);
}
void heapify(int heap[], int n){
   int i, j, c, root, temp;
   for (j = n - 1; j >= 0; j--) {
      temp = heap[0];
      heap[0] = heap[j]; // swap max element with rightmost leaf element
      heap[j] = temp;
      root = 0;
      do {
         c = 2 * root + 1; // left node of root element
         if ((heap[c] < heap[c + 1]) && c < j-1)
            c++;
         if (heap[root]<heap[c] && c<j) { // again rearrange to max heap array
            temp = heap[root];
            heap[root] = heap[c];
            heap[c] = temp;
         }
         root = c;
      } while (c < j);
   }
   printf("\nThe sorted array is: ");
   
   for (i = 0; i < n; i++)
      printf("%d ", heap[i]);
}
int main(){
   int n, i, j, c, root, temp;
   n = 5;
   int heap[10] = {2, 3, 1, 0, 4}; // initialize the array
   build_maxheap(heap, n);
}

输出

Heap array: 4 3 1 0 2 
The sorted array is: 0 1 2 3 4 

#include <iostream>
using namespace std;
void heapify(int[], int);
void build_maxheap(int heap[], int n){
   int i, j, c, r, t;
   for (i = 1; i < n; i++) {
      c = i;
      do {
         r = (c - 1) / 2;
         if (heap[r] < heap[c]) { // to create MAX heap array
            t = heap[r];
            heap[r] = heap[c];
            heap[c] = t;
         }
         c = r;
      } while (c != 0);
   }
   cout << "Heap array: ";
   for (i = 0; i < n; i++)
      cout <<heap[i]<<" ";
   heapify(heap, n);
}
void heapify(int heap[], int n){
   int i, j, c, root, temp;
   for (j = n - 1; j >= 0; j--) {
      temp = heap[0];
      heap[0] = heap[j]; // swap max element with rightmost leaf element
      heap[j] = temp;
      root = 0;
      do {
         c = 2 * root + 1; // left node of root element
         if ((heap[c] < heap[c + 1]) && c < j-1)
            c++;
         if (heap[root]<heap[c] && c<j) { // again rearrange to max heap array
            temp = heap[root];
            heap[root] = heap[c];
            heap[c] = temp;
         }
         root = c;
      } while (c < j);
   }
   cout << "\nThe sorted array is : ";
   for (i = 0; i < n; i++)
      cout <<heap[i]<<" ";
}
int main(){
   int n, i, j, c, root, temp;
   n = 5;
   int heap[10] = {2, 3, 1, 0, 4}; // initialize the array
   build_maxheap(heap, n);
   return 0;
}

输出

Heap array: 4 3 1 0 2 
The sorted array is : 0 1 2 3 4 

import java.io.*;
public class HeapSort {
   static void build_maxheap(int heap[], int n) {
      for (int i = 1; i < n; i++) {
         int c = i;
         do {
            int r = (c - 1) / 2;
            if (heap[r] < heap[c]) { // to create MAX heap array
               int t = heap[r];
               heap[r] = heap[c];
               heap[c] = t;
            }
            c = r;
         } while (c != 0);
      }
      System.out.println("Heap array: ");
      for (int i = 0; i < n; i++) {
         System.out.print(heap[i] + " ");
      }
      heapify(heap, n);
   }
   static void heapify(int heap[], int n) {
      for (int j = n - 1; j >= 0; j--) {
         int c;
         int temp = heap[0];
         heap[0] = heap[j]; // swap max element with rightmost leaf element
         heap[j] = temp;
         int root = 0;
         do {
            c = 2 * root + 1; // left node of root element
            if ((heap[c] < heap[c + 1]) && c < j-1)
               c++;
            if (heap[root]<heap[c] && c<j) { // again rearrange to max heap array
               temp = heap[root];
               heap[root] = heap[c];
               heap[c] = temp;
            }
            root = c;
         } while (c < j);
      }
      System.out.println("\nThe sorted array is: ");
      for (int i = 0; i < n; i++) {
         System.out.print(heap[i] + " ");
      }
   }
   public static void main(String args[]) {
      int heap[] = new int[10];
      heap[0] = 4;
      heap[1] = 3;
      heap[2] = 1;
      heap[3] = 0;
      heap[4] = 2;
      int n = 5;
      build_maxheap(heap, n);
   }
}

输出

Heap array: 
4 3 1 0 2 
The sorted array is: 
0 1 2 3 4 

def heapify(heap, n, i):
   maximum = i
   l = 2 * i + 1
   r = 2 * i + 2
   # if left child exists
   if l < n and heap[i] < heap[l]:
      maximum = l
   # if right child exits
   if r < n and heap[maximum] < heap[r]:
      maximum = r
   # root
   if maximum != i:
      heap[i],heap[maximum] = heap[maximum],heap[i] # swap root.
      heapify(heap, n, maximum)
def heapSort(heap):
   n = len(heap)
   # maxheap
   for i in range(n, -1, -1):
      heapify(heap, n, i)
   # element extraction
   for i in range(n-1, 0, -1):
      heap[i], heap[0] = heap[0], heap[i] # swap
      heapify(heap, i, 0)
# main
heap = [4, 3, 1, 0, 2]
heapSort(heap)
n = len(heap)
print("Heap array: ")
print(heap)
print ("The Sorted array is: ")
print(heap)

输出

Heap array: 
[0, 1, 2, 3, 4]
The Sorted array is: 
[0, 1, 2, 3, 4]