การเรียงลำดับฮีปขึ้นอยู่กับโครงสร้างข้อมูลไบนารีฮีป ในไบนารีฮีป โหนดย่อยของโหนดหลักมีขนาดเล็กกว่าหรือเท่ากับในกรณีของฮีปสูงสุด และโหนดย่อยของโหนดหลักจะมากกว่าหรือเท่ากับในกรณีของฮีปขั้นต่ำ
ตัวอย่างที่อธิบายขั้นตอนทั้งหมดใน Heap Sort มีดังนี้
อาร์เรย์ดั้งเดิมที่มี 10 องค์ประกอบก่อนการเรียงลำดับคือ −
| 20 | 7 | 1 | 54 | 10 | 15 | 90 | 23 | 77 | 25 |
อาร์เรย์นี้สร้างขึ้นในฮีปสูงสุดแบบไบนารีโดยใช้ max-heapify ฮีปสูงสุดนี้แสดงเป็นอาร์เรย์ดังนี้
| 90 | 77 | 20 | 54 | 25 | 15 | 1 | 23 | 7 | 10 |
องค์ประกอบรากของฮีปสูงสุดจะถูกแยกออกมาและวางไว้ที่ส่วนท้ายของอาร์เรย์ จากนั้น max heapify จะถูกเรียกให้แปลงองค์ประกอบที่เหลือเป็นฮีปสูงสุด นี้จะทำจนในที่สุดอาร์เรย์ที่เรียงลำดับได้รับซึ่งได้รับดังต่อไปนี้ −
| 1 | 7 | 10 | 15 | 20 | 23 | 25 | 54 | 77 | 90 |
โปรแกรมจัดเรียงอาร์เรย์ 10 องค์ประกอบโดยใช้อัลกอริธึมการจัดเรียงแบบฮีปมีดังต่อไปนี้
ตัวอย่าง
#include<iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
int temp;
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) {
temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
int temp;
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--) {
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
int main() {
int arr[] = { 20, 7, 1, 54, 10, 15, 90, 23, 77, 25};
int n = 10;
i nt i;
cout<<"Given array is: "<<endl;
for (i = 0; i *lt; n; i++)
cout<<arr[i]<<" ";
cout<<endl;
heapSort(arr, n);
printf("\nSorted array is: \n");
for (i = 0; i < n; ++i)
cout<<arr[i]<<" ";
} ผลลัพธ์
Given array is: 20 7 1 54 10 15 90 23 77 25 Sorted array is: 1 7 10 15 20 23 25 54 77 90
ในโปรแกรมข้างต้น ฟังก์ชัน heapify() ใช้เพื่อแปลงองค์ประกอบให้เป็นฮีป ฟังก์ชันนี้เป็นฟังก์ชันแบบเรียกซ้ำและสร้างฮีปสูงสุดโดยเริ่มจากองค์ประกอบที่เรียกว่า i.e. i ในกรณีนี้ ข้อมูลโค้ดที่แสดงให้เห็นมีดังต่อไปนี้
void heapify(int arr[], int n, int i) {
int temp;
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) {
temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
} ฟังก์ชัน heapSort() ขององค์ประกอบอาร์เรย์โดยใช้การเรียงลำดับแบบฮีป มันเริ่มต้นจากโหนดที่ไม่ใช่ใบไม้และเรียก heapify() ในแต่ละโหนด สิ่งนี้จะแปลงอาร์เรย์เป็นไบนารีสูงสุดฮีป ดังแสดงดังนี้ −
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
หลังจากนี้ ฟังก์ชัน heapSort() จะนำองค์ประกอบรากในการวนซ้ำ for แต่ละครั้งและวางไว้ที่ส่วนท้ายของอาร์เรย์ จากนั้น heapify() จะถูกเรียกเพื่อให้แน่ใจว่าองค์ประกอบที่เหลือเป็นฮีปสูงสุด ในที่สุด องค์ประกอบทั้งหมดจะถูกลบออกจากฮีปสูงสุดโดยใช้วิธีนี้และได้อาร์เรย์ที่จัดเรียงแล้ว ดังแสดงไว้ดังนี้
for (int i = n - 1; i >= 0; i--) {
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
} ในฟังก์ชัน main() อันดับแรกจะแสดงอาร์เรย์ จากนั้น ฟังก์ชัน heapSort() จะถูกเรียกเพื่อเรียงลำดับอาร์เรย์ ซึ่งได้รับจากข้อมูลโค้ดต่อไปนี้
cout<<"Given array is: "<<endl; for (i = 0; i < n; i++) cout<<arr[i]<<" "; cout<<endl; heapSort(arr, n);
ในที่สุดอาร์เรย์ที่เรียงลำดับจะปรากฏขึ้น ดังแสดงด้านล่าง
printf("\nSorted array is: \n");
for (i = 0; i < n; ++i)
cout<<arr[i]<<" "; 