堆排序演算法

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]
列印頁面
上一頁
下一頁
廣告