堆排序算法

Table of content
上一页
下一页

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

堆是一个几乎完整的二叉树，其中父节点可以是最小值或最大值。根节点为最小值的堆称为最小堆，根节点为最大值的堆称为最大堆。堆排序算法使用这两种方法处理输入数据。

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

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

  • 删除根元素并重复此过程，直到所有输入元素都被处理。

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

堆化方法

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

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

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

要了解更多关于堆化算法的信息，请点击此处。

堆排序算法

如下算法所述，排序算法首先通过调用构建最大堆算法来构建堆ADT，并删除根元素将其与叶节点上的最小值节点交换。然后应用堆化方法相应地重新排列元素。

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

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

heap_data_structure 23_to_3 23_to_12 14_to_3 14_to_12 18_to_9.jpg

堆化算法

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

根节点为23，因此弹出23，并将18设为下一个根，因为它是堆中下一个最大节点。

23_popped

现在，在23之后弹出18，并将其替换为14。

18_popped

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

14_popped

弹出12并替换为10。

12_popped

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

10_popped

此处，当前根元素9被弹出，并且元素8和3保留在树中。

9_popped

然后，弹出8，树中只剩下3。

8_popped.jpg

在对给定堆完成堆排序操作后，排序后的元素如下所示：

all_element_popped.jpg

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

最终排序列表为：

3 8 9 10 12 14 18 23

实现

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

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

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]
打印页面
上一页
下一页
广告