java 實現 堆排序算法

Heap Sort is a comparison-based sorting algorithm that makes use of a different data structure called Binary Heaps. Let us understand some important terms,

堆排序是一種基于比較的排序算法，該算法利用稱為二進制堆的不同數據結構。 讓我們了解一些重要的術語，

1. Complete Binary Tree: A tree is complete when all the levels (except of course the last level) are completely filled, i.e. all the parent nodes have two children nodes each and all the nodes are as far left as possible which means first we fill the left node and then the right.

   完整的二叉樹 ：當所有級別(當然，最后一個級別除外)都被完全填充時，即所有樹的父節點都有兩個子節點，并且所有節點都盡可能靠左，這意味著一棵樹完成了。左節點，然后右。

2. Binary Heap: It is a complete binary tree but there is an order of elements from parent to children in Binary Heap. They can be of two types,

   Binary Heap ：這是一個完整的二叉樹，但是Binary Heap中從父級到子級都有一個元素順序。 它們可以有兩種類型，

   1. Max Binary Heap or Max Heap where the parent node is greater than its two children nodes.
   2. 最大父節點大于其兩個子節點的最大二進制堆或最大堆 。
   3. Min Binary Heap or Min Heap where the parent node is smaller than its children nodes.最小二進制堆或最小堆 ，其中父節點小于其子節點。

The main() function of Heap Sort is to call the heapify() function which leads to the building of a max heap and then the largest element is stored in the last position of the array as so on till only one element is left in the heap. Array representation of heap is preferred because it occupies less space and also it is easy to reference the root and children nodes.

堆排序的main()函數將調用heapify()函數，該函數將導致建立最大堆，然后將最大元素存儲在數組的最后一個位置，依此類推，直到在數組中只剩下一個元素為止。堆。 堆的數組表示形式是首選的，因為它占用較少的空間，并且易于引用根節點和子節點。

Algorithm (Considering Max heap):

算法(考慮最大堆)：

1. First, we form a Max Heap such that the first node or the root node is the largest element. This step takes O(N) time complexity.

   首先，我們形成一個最大堆，以使第一個節點或根節點成為最大元素。 此步驟需要O(N)時間復雜度。

2. Next, we swap the root element with the last element of the heap and reduce the size of heap by 1.

   接下來，我們將根元素與堆的最后一個元素交換，并將堆的大小減小1。

3. Repeat steps 1 and 2 are till only 1 element is left.

   重復步驟1和2，直到僅剩1個元素。

How to build the Heap?

如何建立堆？

The heapify procedure can be applied to a node only when its children nodes are heapified. Therefore, we start the heapification with the last non-leaf node. To find the first non-leaf node, the following formula is used:?First non-leafy node = lower bound (n/2)

僅當對子節點進行堆化時，才能將heapify過程應用于該節點。 因此，我們從最后一個非葉子節點開始堆化 。 要找到第一個非葉子節點，請使用以下公式： 第一個非葉子節點=下界(n / 2)

Hence, if there are 5 elements in the heap, the first non-leafy node would be the second node or the node at index 1.

因此，如果堆中有5個元素，則第一個非葉節點將是第二個節點或索引為1的節點。

Pseudo Code:

偽代碼：

Heap_Sort (arr[], n)
{
// Creating the initial Max heap
for i = n/2 – 1 to 0:
heapify(arr, n, i)
// Swapping largest element and repeating the steps further
for i = n-1 to 0:
swap(arr[0], arr[i]
heapify(arr, n, i)
}
Heapify (arr[], n, i)
{
int largest = i;
int left = 2*i + 1; // Left child
int right = 2*i + 2; // Right child
// Check if left child exists and is larger than root
If (left < n && arr[left] > arr[largest]):
Largest = left;
// Check if right child exists and is larger than largest
If (right < n && arr[right] > arr[largest]):
largest = right;
// Change root, if root is not the largest
If(largest != i)
Swap(arr[i], arr[largest])
Heapify(arr, n, largest); //Repeat till max heap is obtained
}

Time Complexity:

時間復雜度：

The time complexity of Heap sort is:

堆排序的時間復雜度為：

1. Worst Case = O(N log N)

   最壞情況= O(N log N)

2. Average Case = ?(N log N)

   平均情況=?(N log N)

3. Best Case = Ω(N log N)

   最佳情況=Ω(N log N)

4. Space Complexity: ?(1)

   空間復雜度：?(1)

The time complexity of Heapify is O(log N) and that of Build_heap / Heap_Sort is O(N). The overall complexity of Heap_Sort is therefor, O(N log N).

Heapify的時間復雜度為O(log N)，而Build_heap / Heap_Sort的時間復雜度為O(N)。 因此，Heap_Sort的總體復雜度為O(N log N)。

Heap Sort Implementation:

堆排序實現：

#include <stdio.h>
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i)
{
int left, right, largest;
largest = i;
left = 2 * i + 1;
right = 2 * i + 2;
// Check if left child exists and is larger than its parent
if (left < n && arr[left] > arr[largest])
largest = left;
// Check if right child exists and larger than its parent
if (right < n && arr[right] > arr[largest])
largest = right;
// if root is not the largest
if (largest != i) {
swap(&arr[i], &arr[largest]); //make root the largest
heapify(arr, n, largest); // Apply heapify to the largest node
}
}
void heap_sort(int arr[], int n)
{
int i;
for (i = (n / 2) - 1; i >= 0; i--)
heapify(arr, n, i);
for (i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]); //Move the largest element at root to the end
heapify(arr, i, 0); //Apply heapify to reduced heap
}
}
int main()
{
int arr[] = { 20, 13, 34, 56, 12, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
heap_sort(arr, n);
printf("\nAfter performing Heap Sort:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}

Output:

輸出：

Array:
20 13 34 56 12 10
After performing Heap Sort:
10 12 13 20 34 56

Applications:

應用范圍：

1. Job Scheduling: In Linux OS is used due to low space and time complexity

   作業調度 ：由于空間和時間復雜度低，在Linux OS中使用

2. Graph Algorithms: Djikstar's Algorithm, Prim's Algorithm and Huffman Coding

   圖算法 ：Djikstar算法，Prim算法和霍夫曼編碼

翻譯自: https://www.includehelp.com/c-programs/implement-heap-sort-algorithm.aspx

java 實現 堆排序算法