อัลกอริทึมการเรียงลำดับฮีป (พร้อมโค้ดใน Python และ C++)

อัลกอริทึมการเรียงลำดับฮีปคืออะไร

Heap Sort เป็นอัลกอริทึมการเรียงลำดับที่นิยมใช้กันและรวดเร็วที่สุดอัลกอริทึมหนึ่ง โดยสร้างขึ้นจากโครงสร้างข้อมูลแบบไบนารีทรีที่สมบูรณ์ เราจะค้นหาองค์ประกอบสูงสุดและวางไว้ที่ด้านบนสุดของฮีปสูงสุด เราจะวางไว้ที่โหนดหลักของไบนารีทรี

สมมติว่าได้รับอาร์เรย์ ข้อมูล = [10,5, 7, 9, 4, 11, 45, 17, 60].

ในอาเรย์ ถ้าดัชนี i-th (i=0,1,2,3 …) เป็นโหนดหลัก ดังนั้น (2i+1) และ (2i+2) จะเป็นลูกด้านซ้ายและขวา การสร้างแผนผังไบนารีที่สมบูรณ์ด้วยอาเรย์นี้จะมีลักษณะดังนี้:

เราจะดำเนินการ heapify ตั้งแต่ต้นจนจบอาร์เรย์ ในตอนแรก หากเราแปลงอาร์เรย์เป็นทรี อาร์เรย์จะมีลักษณะดังภาพด้านบน เราจะเห็นว่าอาร์เรย์ไม่ได้รักษาคุณสมบัติของ heap ใดๆ (min-heap หรือ max heap) เราจะได้อาร์เรย์ที่เรียงลำดับแล้วโดยดำเนินการ heapify สำหรับโหนดทั้งหมด

การประยุกต์ใช้การเรียงลำดับฮีป

ต่อไปนี้เป็นการใช้งานอัลกอริทึมการเรียงลำดับฮีป:

การสร้าง "คิวลำดับความสำคัญ" จำเป็นต้องมีการเรียงลำดับฮีป เนื่องจากฮีปเรียงลำดับจะเก็บองค์ประกอบไว้หลังจากการแทรกแต่ละครั้ง
โครงสร้างข้อมูลฮีปมีประสิทธิภาพในการค้นหาเค^th องค์ประกอบที่ใหญ่ที่สุดในอาร์เรย์ที่กำหนด
Linux Kernel ใช้การเรียงลำดับฮีปเป็นค่าเริ่มต้น อัลกอริทึมการเรียงลำดับ เนื่องจากมีความซับซ้อนของพื้นที่ O (1)

สร้างการเรียงลำดับฮีปด้วยตัวอย่าง

ที่นี่เราจะสร้าง max heap จากไบนารีทรีที่สมบูรณ์ดังต่อไปนี้

โหนดย่อยคือ 17, 60, 4, 11 และ 45 โหนดย่อยเหล่านี้ไม่มีโหนดย่อย นั่นคือเหตุผลว่าทำไมจึงเป็นโหนดย่อย ดังนั้นเราจะเริ่มวิธี heapify จากโหนดหลัก นี่คือขั้นตอน:

ขั้นตอน 1) เลือกแผนผังย่อยซ้ายสุด หากโหนดย่อยมีขนาดใหญ่กว่า ให้สลับโหนดหลักกับโหนดย่อย

ที่นี่โหนดหลักคือ 9 และโหนดย่อยคือ 17 และ 60 เนื่องจาก 60 เป็นโหนดที่ใหญ่ที่สุด 60 และ 9 จะถูกสลับเพื่อรักษา กองสูงสุด.

ขั้นตอน 2) ตอนนี้ ทรีย่อยซ้ายสุดถูกฮีปแล้ว โหนดพาเรนต์ถัดไปคือ 7 พาเรนต์นี้มีโหนดย่อยสองโหนด และโหนดที่ใหญ่ที่สุดคือ 45 ดังนั้น 45 และ 7 จะถูกสลับ

ขั้นตอน 3) โหนด 60 และ 4 มีโหนดหลัก 5 เนื่องจาก “5” มีขนาดเล็กกว่าโหนดย่อย 60 จึงจะถูกสลับ

ขั้นตอน 4) ตอนนี้โหนด 5 มีโหนดลูก 17,9 นี่ไม่ได้รักษาคุณสมบัติฮีปสูงสุด ดังนั้น 5 จะถูกแทนที่ด้วย 17

ขั้นตอน 5) โหนด 10 จะถูกสลับด้วย 60 จากนั้นจึงสลับด้วย 17 กระบวนการจะมีลักษณะดังต่อไปนี้

ขั้นตอน 6) จนถึงขั้นตอนที่ 5 เราได้สร้างฮีปสูงสุดแล้ว ทุกโหนดหลักมีขนาดใหญ่กว่าโหนดย่อย โหนดรูทมีค่าสูงสุด (60)

หมายเหตุ ในการสร้างอาร์เรย์ที่เรียงลำดับ เราจำเป็นต้องแทนที่โหนดที่มีค่าสูงสุดด้วยตัวตายตัวแทน

กระบวนการนี้เรียกว่า “สกัดสูงสุด- เนื่องจาก 60 เป็นโหนดสูงสุด เราจะกำหนดตำแหน่งให้เป็นดัชนีที่ 0 และสร้างฮีปโดยไม่มีโหนด 60

ขั้นตอน 7) เมื่อลบ 60 แล้วค่าสูงสุดถัดไปคือ 45 เราจะดำเนินการ "แยก Max" อีกครั้งจากโหนด 45

คราวนี้เราจะได้รับ 45 และแทนที่โหนดรูทด้วยตัวตายตัวแทน 17

เราจำเป็นต้องดำเนินการ”สารสกัดสูงสุด” จนกว่าองค์ประกอบทั้งหมดจะถูกจัดเรียง

หลังจากทำตามขั้นตอนเหล่านี้จนกระทั่งเราแยกค่าสูงสุดทั้งหมดออกมาแล้ว เราจะได้อาร์เรย์ดังต่อไปนี้

ไบนารีฮีปคืออะไร?

Binary Heap เป็นแบบที่สมบูรณ์ ต้นไม้ไบนารี โครงสร้างข้อมูล. ในโครงสร้างต้นไม้ชนิดนี้ โหนดพาเรนต์จะมีขนาดใหญ่กว่าหรือเล็กกว่าโหนดย่อย หากโหนดพาเรนต์มีขนาดเล็ก ฮีปจะเรียกว่า “มินฮีป” และหากโหนดพาเรนต์มีขนาดใหญ่กว่า ฮีปจะเรียกว่า “แม็กซ์ฮีป”

นี่คือตัวอย่างของฮีปขั้นต่ำและฮีปสูงสุด

ในรูปด้านบน หากคุณสังเกตเห็น “Min Heap” โหนดหลักจะมีขนาดเล็กกว่าโหนดลูกเสมอ ที่หัวต้นไม้ เราสามารถหาค่าที่น้อยที่สุดได้ 10

ในทำนองเดียวกัน สำหรับ "Max Heap" โหนดหลักจะมีขนาดใหญ่กว่าโหนดลูกเสมอ องค์ประกอบสูงสุดอยู่ที่โหนดส่วนหัวสำหรับ "Max Heap"

Heapify คืออะไร?

“Heapify” คือหลักการของฮีปที่รับรองตำแหน่งของโหนด ใน Heapify ฮีปสูงสุดจะรักษาความสัมพันธ์กับโหนดหลักและโหนดย่อยเสมอ และโหนดหลักจะมีขนาดใหญ่กว่าโหนดย่อย

ตัวอย่างเช่น หากมีการเพิ่มโหนดใหม่ เราจำเป็นต้องปรับเปลี่ยนรูปร่างของฮีป อย่างไรก็ตาม เราอาจจำเป็นต้องเปลี่ยนแปลงหรือสลับโหนดหรือจัดเรียงอาร์เรย์ใหม่ กระบวนการปรับเปลี่ยนรูปร่างของฮีปนี้เรียกว่า “heapify”

นี่คือตัวอย่างวิธีการทำงานของ heapify:

การเพิ่มโหนดใหม่และ Heapify — การเพิ่มโหนดใหม่และฮีพฟิฟาย

นี่คือขั้นตอนสำหรับ heapify:

ขั้นตอน 1) เพิ่มโหนด 65 เป็นลูกที่ถูกต้องของโหนด 60

ขั้นตอน 2) ตรวจสอบว่าโหนดที่เพิ่มใหม่มีค่ามากกว่าโหนดหลักหรือไม่

ขั้นตอน 3) เนื่องจากมันมากกว่าโหนดพาเรนต์ เราจึงสลับโหนดย่อยที่ถูกต้องกับโหนดพาเรนต์

วิธีการสร้างฮีป

ก่อนที่จะสร้างฮีปหรือสร้างต้นไม้แบบฮีป เราจำเป็นต้องทราบก่อนว่าเราจะจัดเก็บมันอย่างไร เนื่องจากฮีปเป็นต้นไม้แบบไบนารีที่สมบูรณ์ จึงควรใช้ แถว เพื่อเก็บข้อมูลของฮีป

สมมติว่าอาร์เรย์มีองค์ประกอบทั้งหมด n รายการ หากดัชนี “i” เป็นโหนดหลัก โหนดด้านซ้ายจะอยู่ที่ดัชนี (2i+1)และโหนดที่ถูกต้องจะอยู่ที่ดัชนี (2i+2)- เราสมมติว่าดัชนีอาร์เรย์เริ่มต้นจาก 0

ด้วยวิธีนี้ เราจะเก็บค่า max heap ลงในรูปแบบอาร์เรย์ดังต่อไปนี้:

การแสดงตามอาร์เรย์ของ Max Heap — การแสดงค่าฮีปสูงสุดตามอาร์เรย์

อัลกอริธึม heapify จะรักษาคุณสมบัติของ heap ไว้ หากโหนดหลักไม่มีค่าสุดขั้ว (น้อยกว่าหรือมากกว่า) โหนดหลักจะสลับกับโหนดย่อยที่มีค่าสุดขั้วมากที่สุด

ต่อไปนี้เป็นขั้นตอนในการสร้าง heap สูงสุด:

ขั้นตอน 1) เริ่มจากโหนดใบ

ขั้นตอน 2) ค้นหาค่าสูงสุดระหว่างผู้ปกครองและลูก

ขั้นตอน 3) สลับโหนดหากโหนดลูกมีค่ามากกว่าโหนดหลัก

ขั้นตอน 4) ขึ้นไปหนึ่งระดับ

ขั้นตอน 5) ทำตามขั้นตอนที่ 2,3,4 จนกระทั่งถึงดัชนี 0 หรือเรียงลำดับทั้งแผนผัง

นี่คือรหัสเทียมสำหรับ heapify แบบเรียกซ้ำ (heap สูงสุด):

def heapify():
  input→ array, size, i
  largest = i
  left = 2*i + 1
  right = 2*i + 2
if left<n and array[largest ] < array[left]:
  largest = left
if right<n and array[largest ] < array[right]:
  largest = right
If largest not equals i:
  swap(array[i],array[largest])
  heapify(array,n,largest)

รหัสหลอกสำหรับการเรียงลำดับฮีป

นี่คือรหัสหลอกสำหรับอัลกอริทึมการเรียงลำดับฮีป:

Heapify(numbers as an array, n as integer, i as integer):
  largest = i
  left = 2i+1
  right= 2i+2
if(left<=n) and (numbers[i]<numbers[left])
  largest=left
if(right<=n) and (numbers[i]<numbers[right])
  largest=right
if(largest  != i)
  swap(numbers[i], numbers[largest])
  Heapify(numbers,n,largest)
HeapSort(numbers as an array):
  n= numbers.size()
for i in range n/2 to 1
  Heapify(numbers,n,i)
for i in range n to 2
  Swap numbers[i] with numbers[1]
  Heapify(numbers,i,0)

ตัวอย่างโค้ดการเรียงลำดับฮีปใน C++

#include <iostream>
using namespace std;
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;
}
void heapify(int numbers[], int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && numbers[left] < numbers[largest])
    {
        largest = left;
    }
    if (right < n && numbers[right] < numbers[largest])
    {
        largest = right;
    }
    if (largest != i)
    {
	//uncomment the following line to see details in output
        //cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
        swap(numbers[i], numbers[largest]);
        heapify(numbers, n, largest);
    }
}
void heapSort(int numbers[], int n)
{
    for (int i = n/2 - 1; i >= 0; i--)
    {
        heapify(numbers, n, i);
//uncomment the following line to see details in output
 //cout<<"Heapify:\t";
  //display(numbers,n);
    }
    for (int i = n - 1; i >= 0; i--)
    {
        swap(numbers[0], numbers[i]);
        heapify(numbers, i, 0);
    }
}
int main()
{
    int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    cout<<"Initial Array:\t";
    display(numbers,size);
    heapSort(numbers, size);
    cout<<"Sorted Array (descending order):\t";
    display(numbers, size);
}

Output:

Initial Array:  10      5       7       9       4       11      45      17      60
Sorted Array (descending order):  60      45      17      11      10      9       7       5       4

ตัวอย่างโค้ดการเรียงลำดับฮีปใน Python

def display(arr):
    for i in range(len(arr)):
    print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
    largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
    largest = left
if right < n and numbers[right] < numbers[largest]:
    largest = right
if largest != i:
    numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
    for i in range(n //2,-1,-1):
        heapify(items, n, i) for i in range(n - 1, -1, -1):
        items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)

Output:

Initial List:   10      5       7       9       4       11      45      17      60
After HeapSort: 60      45      17      11      10      9       7       5       4

การวิเคราะห์ความซับซ้อนของเวลาและพื้นที่ของการเรียงลำดับแบบกอง

มีความซับซ้อนของเวลาและความซับซ้อนของพื้นที่ที่เราสามารถวิเคราะห์ได้สำหรับการเรียงลำดับแบบฮีป สำหรับความซับซ้อนของเวลา เรามีกรณีดังต่อไปนี้:

เคสที่ดีที่สุด
กรณีเฉลี่ย
กรณีที่เลวร้ายที่สุด

ฮีปถูกนำไปใช้บนแผนผังไบนารีที่สมบูรณ์ ดังนั้นที่ระดับล่างสุดของไบนารีทรี จะมีจำนวนโหนดสูงสุด หากระดับล่างสุดไม่มีโหนด ระดับด้านบนก็จะมี n/2 โหนด

ในตัวอย่างนี้ ระดับ 3 มีสี่รายการ ระดับ 2 มีสองรายการ และระดับ 1 มีหนึ่งรายการ หากมีทั้งหมด n จำนวนรายการ ความสูงหรือระดับรวมจะเป็น เข้าสู่ระบบ₂(น). ดังนั้น การแทรกองค์ประกอบเดียวอาจใช้เวลาสูงสุดในการวนซ้ำ Log(n)

เมื่อเราต้องการดึงค่าสูงสุดจากฮีป เราเพียงแค่ดึงโหนดราก จากนั้นรันฮีปฟิวซ์อีกครั้ง ฮีปฟิวซ์แต่ละตัวจะดึงค่าสูงสุดจากโหนดราก เข้าสู่ระบบ₂(n) เวลา. การแยกค่าสูงสุดจะใช้เวลา O(1)

ความซับซ้อนของเวลาที่ดีที่สุดสำหรับอัลกอริทึมการเรียงลำดับฮีป

เมื่อองค์ประกอบทั้งหมดได้รับการจัดเรียงในอาร์เรย์แล้ว จะต้องใช้เวลา O(n) ในการสร้างฮีป เพราะหากเรียงลำดับรายการแล้วการแทรกรายการจะใช้เวลาคงที่นั่นคือ O(1)

ดังนั้น จะต้องใช้เวลา O(n) ในการสร้าง max-heap หรือ min-heap ในกรณีที่ดีที่สุด

ความซับซ้อนของเวลาเคสโดยเฉลี่ยสำหรับอัลกอริทึมการเรียงลำดับฮีป

การแทรกรายการหรือการดึงข้อมูลสูงสุดใช้เวลา O(log(n)) ดังนั้นความซับซ้อนของเวลาเฉลี่ยสำหรับอัลกอริทึมการเรียงลำดับแบบกองคือ O(n บันทึก(n))

ความซับซ้อนของเวลาในกรณีที่แย่ที่สุดสำหรับอัลกอริทึมการเรียงลำดับแบบฮีป

คล้ายกับกรณีทั่วไป ในสถานการณ์เลวร้ายที่สุด เราอาจดำเนินการ heapify n ครั้ง แต่ละครั้งจะใช้เวลา O(log(n)) ดังนั้น ความซับซ้อนของเวลาในกรณีเลวร้ายที่สุดจะเป็นดังนี้ O(n บันทึก(n))

ความซับซ้อนของพื้นที่สำหรับอัลกอริทึมการเรียงลำดับแบบฮีป

การเรียงลำดับแบบฮีปเป็นอัลกอริทึมที่ออกแบบขึ้นเอง ซึ่งหมายความว่าไม่จำเป็นต้องใช้หน่วยความจำพิเศษหรือหน่วยความจำชั่วคราวเพื่อดำเนินการงาน หากเราดูการใช้งานจริง เราจะสังเกตเห็นว่าเราใช้ swap () เพื่อดำเนินการแลกเปลี่ยนโหนด ไม่จำเป็นต้องใช้รายการหรืออาร์เรย์อื่น ดังนั้นความซับซ้อนของพื้นที่จึงเท่ากับ O(1)