© metamorworks/Shutterstock.com

เมื่อจัดเรียงอาร์เรย์ของข้อมูล สิ่งสำคัญคือต้องทำความคุ้นเคยกับอัลกอริทึมการเรียงลำดับ ในโครงสร้างข้อมูล การเรียงลำดับเป็นการจัดเรียงข้อมูลในรูปแบบเฉพาะตามความสัมพันธ์เชิงเส้นระหว่างรายการข้อมูล

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

Heap Sort คืออะไร: คำนิยามที่แน่นอน

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

การจัดเรียงฮีปโดยพื้นฐานแล้ว มีสองขั้นตอนที่เกี่ยวข้อง:

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

อัลกอริทึมการจัดเรียงแบบฮีปทำงานอย่างไร

นี่คือวิธีการใช้อัลกอริทึมการจัดเรียงแบบฮีป:

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

นี่คืออัลกอริทึม

HeapSort(arr)

CreateMaxHeap(arr)

for i=length(arr) เป็น 2

    สลับ arr[1] กับ arr[i]

        heap_size[arr]=heap_size[arr] ? 1

        MaxHeapify(arr,1)

จบ        

มาตรวจสอบขั้นตอนกันอีกหน่อย

ขั้นตอนที่ 1: สร้างค่าสูงสุด-heap

CreateMaxHeap(arr)

    heap_size(arr)=length(arr)

    สำหรับ i=length(arr)/2 ถึง 1

   MaxHeapify(arr,i)

   End 

ในอัลกอริทึมนี้ เราจะต้องสร้าง max-heap อย่างที่เราทราบกันดีว่าใน max-heap ค่าที่ใหญ่ที่สุดคือค่ารูท แต่ละโหนดพาเรนต์ต้องมีค่ามากกว่าโหนดย่อยที่เกี่ยวข้อง

ลองนึกดูว่าเรามีรายการค่าที่ไม่เรียงลำดับด้านล่าง:

[14, 11, 2, 20, 3, 10 , 3]

โดยการวางค่าของเราลงในโครงสร้างข้อมูลแบบ max-heap รายการของเราจะมีลักษณะดังนี้:

[20, 11, 14, 2, 10, 5 , 3]

เราสามารถนำเสนอ max-heap ข้างต้นได้ดังนี้:

การนำเสนอ max-heap.

©”TNGD”.com

ขั้นตอนที่ 2: นำรากของ heap ออก

ในการจัดเรียงข้อมูล เราจะแยกและกำจัดค่าที่ใหญ่ที่สุดออกจากฮีปซ้ำๆ จนกว่าจะว่างเปล่า หากเราปฏิบัติตามหลักการของฮีป เราสามารถคาดการณ์ได้ว่าค่าที่ใหญ่ที่สุดจะอยู่ที่รูทของฮีป

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

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

ขั้นตอนที่ 3: ฮีปลง (กู้คืนฮีป)

ค่ารูทไม่ใช่ค่าที่มากกว่า หลักการฮีปคือ ถูกละเมิดเนื่องจากผู้ปกครองต้องมีค่ามากกว่าคุณค่าของเด็ก

อย่างไรก็ตาม ปัญหานี้มีวิธีแก้ไข! เราจะต้องทำให้เป็นกอง ซึ่งเกี่ยวข้องกับการเพิ่มค่าที่ส่วนท้ายของกอง และดำเนินการตามโครงสร้างข้อมูลของคุณจนกว่าคุณจะพบตำแหน่งที่เหมาะสม หากต้องการลดจำนวนลง คุณต้องเปรียบเทียบค่ารูทใหม่กับลูกของมัน เลือกลูกที่มีค่ามากกว่า และสลับกับค่ารูท ค่อยๆ ลงกองจนกว่าจะสมดุล

ภาพประกอบของกระบวนการ heapify down

©”TNGD”.com

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

ขั้นตอนที่ 4: ทำซ้ำ

คุณจะต้องทำซ้ำขั้นตอนการเปลี่ยนรูทและสุดท้าย นำค่าที่ใหญ่ที่สุดออก และปรับสมดุลของฮีปใหม่ ตราบใดที่โครงสร้างข้อมูลมีขนาดมากกว่า 1 เมื่อตรงตามเงื่อนไขนี้ คุณจะมีชุดของค่าที่เรียงลำดับ

ความซับซ้อนของการเรียงลำดับฮีป

ความซับซ้อนของเวลา

นี่คือความซับซ้อนของเวลาของการจัดเรียงแบบฮีปในกรณีที่ดีที่สุด กรณีเฉลี่ย และกรณีที่เลวร้ายที่สุด

<ตาราง >กรณีความซับซ้อนของเวลากรณีที่ดีที่สุดO(n log n)กรณีเฉลี่ยO(n log n)กรณีเลวร้ายที่สุดO (n log n)

Best Case Complexity: เกิดขึ้นเมื่ออาร์เรย์ถูกจัดเรียงแล้ว นั่นคือไม่จำเป็นต้องเรียงลำดับ O(n log n) คือเวลาที่ซับซ้อนที่สุดของการจัดเรียงแบบฮีปความซับซ้อนของกรณีเฉลี่ย: เกิดขึ้นเมื่อองค์ประกอบในอาร์เรย์ไม่ได้ถูกจัดเรียงจากน้อยไปมากหรือมากไปน้อยอย่างเหมาะสม ส่งผลให้ คำสั่งที่สับสน O(n log n) คือเวลาเฉลี่ยของความซับซ้อนของกรณีและปัญหาของการจัดเรียงแบบฮีป ความซับซ้อนของกรณีที่เลวร้ายที่สุด: สิ่งนี้จะเกิดขึ้นเมื่อคุณต้องการเรียงลำดับองค์ประกอบอาร์เรย์ในลำดับย้อนกลับ หมายความว่าหากองค์ประกอบเริ่มต้นจากมากไปน้อย คุณจะต้องเรียงลำดับจากน้อยไปหามาก O(n log n) คือเวลาที่ซับซ้อนที่สุดของการจัดเรียงแบบฮีป

ความซับซ้อนของพื้นที่

ความซับซ้อนของพื้นที่ของการจัดเรียงฮีปคือ O(1)

<ตาราง >ความซับซ้อนของพื้นที่O(1)คงที่N0

อัลกอริทึมการจัดเรียงแบบฮีปถูกนำไปใช้อย่างไร?

นี่คือวิธีการจัดเรียงแบบฮีปในภาษาการเขียนโปรแกรม Java

//การจัดเรียงทรีย่อยให้เป็นฮีป ในที่นี้ “i” คือดัชนีรูทโหนดใน arr[] และ “x” คือขนาดฮีป

public class HeapSort {

    public static void sort(int[] arr) {

        int x=arr.length;

      //จัดเรียงอาร์เรย์ใหม่ (สร้างฮีป)

         สำหรับ (int i=x/2 – 1; i >=0; i–)

        heapify(arr, x, i);

      //แยกองค์ประกอบออกจากฮีปทีละรายการ

       สำหรับ (int i=x – 1; i > 0; i–) {

            //เลื่อนรูทเริ่มต้นไปที่จุดสิ้นสุด

            int temp=arr[0];

             arr[0]=arr[i];

             arr[i]=temp;

            //เรียกใช้ฟังก์ชัน heapify สูงสุดบนฮีปที่ลดลง

            heapify(arr, i, 0);

      }

    }

static void heapify(int[] arr, int x, int i) {

    int ใหญ่ที่สุด=i;//เริ่มต้นค่าที่ใหญ่ที่สุดเป็นรูท

    int l=2 * i + 1;//ซ้าย

    int r=2 * i + 2;//ขวา

    //ถ้าชายด์ซ้ายใหญ่กว่าราก

    if (l x && arr[l] > arr[ที่ใหญ่ที่สุด])

    ที่ใหญ่ที่สุด=l;

    //ถ้าลูกที่ถูกต้องใหญ่กว่าลูกที่ใหญ่ที่สุดจนถึงตอนนี้

    if (r x && arr[r] > arr[ใหญ่ที่สุด])

ใหญ่ที่สุด=r;

      //ถ้าใหญ่ที่สุดไม่ใช่ราก

    if (ใหญ่ที่สุด !=i){

  int swap=arr[i];

        arr[i]=arr[ใหญ่ที่สุด];

        arr[ใหญ่ที่สุด]=สลับ;

      //สร้างกลุ่มย่อยที่ได้รับผลกระทบซ้ำๆ

        heapify(arr, x, ใหญ่ที่สุด);

    }

}

//a ฟังก์ชันพิมพ์อาร์เรย์ขนาด x

โมฆะคงที่ printArray(int[]) {

    int x=arr.length;

    สำหรับ (int i=0; i x; ++i)

        System.out.print(arr[i] + ” “);

    System.out.println();

}

//รหัสไดรเวอร์

public static void main (String[] args) {

    int[] arr={ 13, 12, 14, 6, 7, 8 };

    sort(arr);

    System.out.println(“อาร์เรย์ที่เรียงลำดับคือ”);

    printArray(arr);

 }

}

Output

นี่คืออาร์เรย์จำนวนเต็มที่เรียงลำดับจากน้อยไปหามาก

อาร์เรย์ที่เรียงลำดับคือ

6, 7, 8, 12, 13, 14

ข้อดีและข้อเสียของอัลกอริทึมการจัดเรียงแบบฮีป

ข้อดี

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

ข้อเสีย

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

การประยุกต์ใช้การจัดเรียงแบบกองซ้อน

คุณอาจเคยพบอัลกอริทึมของ Dijkstra ซึ่งใช้การจัดเรียงแบบกองเพื่อกำหนดเส้นทางที่สั้นที่สุด ในโครงสร้างข้อมูล การจัดเรียงแบบฮีปช่วยให้ดึงค่าที่เล็กที่สุด (สั้นที่สุด) หรือใหญ่ที่สุด (ยาวที่สุด) ได้อย่างรวดเร็ว มีแอปพลิเคชันที่หลากหลาย รวมถึงการกำหนดลำดับในสถิติ การจัดการคิวลำดับความสำคัญในอัลกอริทึมของ Prim (หรือที่เรียกว่าแผนผังสแปนนิงขั้นต่ำ) และดำเนินการเข้ารหัส Huffman หรือบีบอัดข้อมูล

ในทำนองเดียวกัน ระบบปฏิบัติการต่างๆ ก็ใช้ Heap อัลกอริทึมการเรียงลำดับสำหรับงานและการจัดการกระบวนการ เนื่องจากเป็นไปตามคิวลำดับความสำคัญ

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

บทสรุป

อัลกอริทึมการเรียงลำดับหรือการค้นหาทุกรายการมีข้อดีและข้อเสีย และการจัดเรียงแบบกองก็ไม่มีข้อยกเว้น อย่างไรก็ตาม ข้อเสียของ Heap Sort นั้นค่อนข้างน้อย ตัวอย่างเช่น ไม่ต้องการพื้นที่หน่วยความจำเพิ่มเติมนอกเหนือจากที่จัดสรรไว้แล้ว

เวลาเป็นอีกปัจจัยหนึ่ง พบว่าความซับซ้อนของเวลาถูกกำหนดโดยใช้ nlog(n) แต่การเรียงลำดับฮีปจริงน้อยกว่า O(nlog(n)) เนื่องจากการแยกจากการจัดเรียงแบบฮีปจะลดขนาด จึงใช้เวลาน้อยลงเมื่อกระบวนการดำเนินต่อไป ดังนั้น Heap Sort จึงได้รับการยกย่องอย่างกว้างขวางว่าเป็นหนึ่งในอัลกอริธึมการเรียงลำดับที่”ดีที่สุด”ในขอบเขตของโครงสร้างข้อมูลด้วยเหตุผลหลายประการ

Heap Sort คืออะไร และคุณใช้อย่างไร คำถามที่พบบ่อย (คำถามที่พบบ่อย) 

Heapify หมายความว่าอย่างไร

Heapify คือกระบวนการสร้างโครงสร้างข้อมูลฮีปจากการแสดงอาร์เรย์ของไบนารี ต้นไม้. กระบวนการนี้สามารถใช้เพื่อสร้าง Max-Heap หรือ Min-Heap เริ่มต้นจากดัชนีสุดท้ายของโหนด non-leaf ในไบนารีทรี ซึ่งดัชนีถูกกำหนดโดย n/2 – 1 Heapify ใช้งานโดยใช้การเรียกซ้ำ

Heap Sort ทำงานอย่างไร

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

คุณจะ”จัดกลุ่ม”ต้นไม้ได้อย่างไร

หากต้องการปรับรูปร่างหรือสร้างไบนารีทรีจำนวนมาก คุณต้องเริ่มด้วยการเลือกโหนดเป็นรูทโหนดของทรีย่อย จากนั้น คุณเปรียบเทียบค่าของรูทโหนดกับค่าของโหนดลูกด้านซ้ายและด้านขวา ถ้าโหนดลูกมีค่าที่ใหญ่กว่า (ในกรณีของฮีปสูงสุด) หรือน้อยกว่า (ในกรณีของฮีปขั้นต่ำ) มากกว่าโหนดรูท ให้คุณสลับค่าของโหนดรูทและโหนดลูกด้วย ค่าที่มากกว่า (หรือน้อยกว่า) หลังจากสลับค่าแล้ว คุณจะวนซ้ำทรีย่อยที่รูทที่โหนดย่อยจนกว่าทรีย่อยทั้งหมดจะตรงตามคุณสมบัติฮีป คุณทำขั้นตอนนี้ซ้ำสำหรับทุกโหนดในทรีจนกว่าทรีทั้งหมดจะตรงตามคุณสมบัติฮีป

ความซับซ้อนของเวลาของการฮีปคือ O(log n) โดยที่ n คือจำนวนโหนดในทรีย่อยที่ถูกฮีป.

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

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

ข้อดีของการจัดเรียงแบบกองคืออะไร

ข้อดีของการเรียงลำดับแบบฮีป ได้แก่ ความซับซ้อนของเวลา O(n log n) ซึ่งเร็วกว่าอัลกอริทึมการเรียงลำดับยอดนิยมอื่นๆ เช่น การเรียงลำดับแบบฟองและการเรียงลำดับแบบแทรก นอกจากนี้ การจัดเรียงแบบฮีปยังมีหน่วยความจำเหลือน้อย เนื่องจากต้องใช้พื้นที่เพิ่มเติมในปริมาณคงที่เท่านั้น

ข้อเสียของการจัดเรียงแบบฮีปคืออะไร

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

By Kaitlynn Clay

ฉันทำงานเป็นผู้เชี่ยวชาญด้าน UX ฉันสนใจในการออกแบบเว็บและการวิเคราะห์พฤติกรรมผู้ใช้ ในวันหยุดของฉัน ฉันมักจะไปเยี่ยมชมพิพิธภัณฑ์ศิลปะเสมอ