โครงสร้างข้อมูลแบบฮีป: ฮีปคืออะไร?
ซาราห์ เฉิน
⚡ สรุปอย่างชาญฉลาด
โครงสร้างข้อมูลแบบฮีป (Heap Data Structure) เป็นต้นไม้ไบนารีสมบูรณ์แบบชนิดพิเศษที่โหนดแม่แต่ละโหนดรักษาความสัมพันธ์เชิงลำดับที่เข้มงวดกับโหนดลูก ทำให้สามารถแทรก ลบ และดำเนินการคิวลำดับความสำคัญได้ในระดับลอการิทึมในงานเรียงลำดับ การจัดตารางเวลา และการประมวลผลกราฟ
โครงสร้างข้อมูลแบบฮีปคืออะไร?
ฮีป (Heap) เป็นโครงสร้างข้อมูลแบบต้นไม้ที่มีความเชี่ยวชาญเฉพาะด้าน โครงสร้างข้อมูลฮีปประกอบด้วยโหนดบนสุดเรียกว่าโหนดราก (โหนดแม่) โหนดที่สองเป็นโหนดลูกซ้ายของโหนดราก และโหนดที่สามเป็นโหนดลูกขวาของโหนดราก โหนดถัดไปจะถูกเติมจากซ้ายไปขวา คีย์ของโหนดแม่จะถูกเปรียบเทียบกับคีย์ของโหนดลูกเพื่อให้เกิดการจัดเรียงที่ถูกต้อง โครงสร้างต้นไม้นี้สามารถมองเห็นภาพได้ง่าย โดยแต่ละเอนทิตีเรียกว่าโหนด และแต่ละโหนดมีคีย์เฉพาะสำหรับการระบุตัวตน
กล่าวโดยง่าย ฮีป (Heap) คือต้นไม้ไบนารีสมบูรณ์ที่ตรงตามคุณสมบัติของฮีป กล่าวคือ โหนดแม่ทุกโหนดมีลำดับที่สอดคล้องกันเมื่อเทียบกับโหนดลูก ซึ่งทำให้เหมาะสำหรับคิวลำดับความสำคัญและอัลกอริทึมการเรียงลำดับแบบฮีป (Heap Sort)
ทำไมคุณถึงต้องการโครงสร้างข้อมูลฮีป?
ต่อไปนี้คือเหตุผลหลักในการใช้ฮีป:
- โครงสร้างข้อมูลแบบฮีป (Heap Data Structure) ช่วยให้สามารถลบและแทรกข้อมูลได้ในเวลาเชิงลอการิทึม – O(log2น)
- ข้อมูลในโครงสร้างต้นไม้ถูกจัดเรียงตามลำดับที่เฉพาะเจาะจง นอกจากการอัปเดตหรือสอบถามค่าต่างๆ เช่น ค่าสูงสุดหรือค่าต่ำสุดแล้ว โปรแกรมเมอร์ยังสามารถค้นหาความสัมพันธ์ระหว่างโหนดแม่และโหนดลูกได้อีกด้วย
- คุณสามารถนำแนวคิดของการ โมเดลวัตถุเอกสาร เพื่อช่วยให้คุณเข้าใจโครงสร้างข้อมูลฮีป (Heap Data Structure) ได้ง่ายขึ้นด้วยภาพประกอบ
- โครงสร้างข้อมูลแบบฮีปช่วยให้การดำเนินการคิวลำดับความสำคัญมีประสิทธิภาพ ซึ่งมีความสำคัญอย่างยิ่งสำหรับอัลกอริธึมกราฟ เช่น เส้นทางที่สั้นที่สุดของไดจ์กสตรา และต้นไม้ครอบคลุมขั้นต่ำของพริม
ประเภทของฮีป
โครงสร้างข้อมูลแบบฮีป (Heap Data Structure) มีอัลกอริธึมหลากหลายสำหรับการจัดการการแทรกและการลบองค์ประกอบ รวมถึงคิวลำดับความสำคัญ (Priority Queue), ฮีปไบนารี (Binary Heap), ฮีปทวิภาค (Binomial Heap) และอื่นๆ เรียงลำดับกอง.
- คิวลำดับความสำคัญ: มันคือกล้ามท้องtracโครงสร้างข้อมูลที่ประกอบด้วยวัตถุที่มีลำดับความสำคัญ วัตถุหรือรายการแต่ละรายการจะมีลำดับความสำคัญที่กำหนดไว้ล่วงหน้า ดังนั้น วัตถุหรือรายการที่ได้รับลำดับความสำคัญสูงกว่าจะได้รับการบริการก่อนรายการอื่นๆ
- ฮีปไบนารี: ฮีปแบบไบนารีเหมาะสำหรับการดำเนินการกับฮีปแบบง่ายๆ เช่น การลบและการแทรกข้อมูล และเป็นรูปแบบการใช้งานเริ่มต้นที่อยู่เบื้องหลังคิวลำดับความสำคัญส่วนใหญ่ในไลบรารีมาตรฐาน
- ฮีปแบบทวินาม: ฮีปแบบทวินาม (Binomial Heap) ประกอบด้วยชุดของต้นไม้แบบทวินาม (Binomial Tree) ที่รวมกันเป็นฮีป ต้นไม้ในฮีปแบบทวินามไม่ใช่ต้นไม้ธรรมดา เนื่องจากมีนิยามที่เข้มงวด จำนวนองค์ประกอบทั้งหมดในต้นไม้แบบทวินามจะมีค่าเท่ากับ 2 เสมอn โหนด
- การเรียงลำดับแบบฮีป: แตกต่างจากอัลกอริธึมการเรียงลำดับส่วนใหญ่ ฮีปซอร์ตใช้พื้นที่ O(1) สำหรับการดำเนินการเรียงลำดับ เป็นอัลกอริธึมการเรียงลำดับแบบเปรียบเทียบ โดยการเรียงลำดับจะเกิดขึ้นในลำดับที่เพิ่มขึ้นโดยการแปลงอินพุตให้เป็นแม็กซ์ฮีปก่อน คุณสามารถมองฮีปซอร์ตได้ว่าเป็นต้นไม้ค้นหาแบบไบนารีที่ได้รับการปรับปรุง
โดยทั่วไป โครงสร้างข้อมูลแบบฮีปจะใช้กลยุทธ์สองแบบ สำหรับข้อมูลเข้า 12 – 8 – 4 – 2 และ 1:
- มินฮีป – ค่าต่ำสุดอยู่ด้านบน
- แม็กซ์ฮีป – ค่าสูงสุดอยู่ด้านบน
มินฮีป
ในโครงสร้างมินฮีป (Min-Heap) โหนดรากจะมีค่าเท่ากับหรือน้อยกว่าค่าของโหนดลูก ดังนั้น รากของมินฮีปจึงมีค่าต่ำสุด นอกจากนี้ มินฮีปยังเป็นต้นไม้ไบนารีสมบูรณ์ (Complete Binary Tree) อีกด้วย
เมื่อคุณมี Min-Heap ในโครงสร้างต้นไม้แล้ว ใบไม้ทั้งหมดจะเป็นตัวเลือกที่เป็นไปได้สำหรับค่าสูงสุด อย่างไรก็ตาม คุณจำเป็นต้องตรวจสอบใบไม้แต่ละใบเพื่อให้ได้ค่า Max-Heap ที่ถูกต้อง
ตัวอย่าง Min-Heap
จากแผนภาพด้านบน คุณจะสังเกตเห็นลำดับที่ชัดเจนจากโหนดรากไปยังโหนดล่างสุด
สมมติว่าคุณเก็บองค์ประกอบไว้ในอาร์เรย์ Array_N[12, 2, 8, 1, 4] ดังที่คุณเห็นจากอาร์เรย์ องค์ประกอบรากนั้นละเมิดลำดับความสำคัญของ Min-Heap เพื่อรักษาคุณสมบัติของ Min-Heap คุณต้องดำเนินการ min-heapify เพื่อสลับองค์ประกอบจนกว่าจะตรงตามกฎของ Min-Heap
แม็กซ์ฮีป
ในโครงสร้าง Max-Heap โหนดแม่หรือโหนดรากจะมีค่าเท่ากับหรือมากกว่าค่าของโหนดลูก โหนดนี้จะเก็บค่าสูงสุด เนื่องจากเป็นต้นไม้ไบนารีสมบูรณ์ คุณจึงสามารถสร้าง Max-Heap จากชุดค่าต่างๆ ได้ในเวลา O(n)
ต่อไปนี้เป็นวิธีการบางส่วนที่นิยมใช้เมื่อทำการติดตั้งระบบ Java แม็กซ์ฮีป:
- เพิ่ม (): เพิ่มองค์ประกอบใหม่ลงในฮีป หากใช้อาร์เรย์ วัตถุจะถูกเพิ่มที่ส่วนท้ายของอาร์เรย์ ในขณะที่ในต้นไม้ไบนารี วัตถุจะถูกเพิ่มจากบนลงล่างแล้วจากซ้ายไปขวา
- ลบ (): วิธีนี้ช่วยให้คุณลบองค์ประกอบแรกออกจากรายการอาร์เรย์ได้ เนื่องจากองค์ประกอบที่ถูกเลื่อนระดับใหม่นั้นไม่ใช่ค่าที่ใหญ่ที่สุดอีกต่อไป วิธี Sift-Down จึงจะผลักองค์ประกอบนั้นไปยังตำแหน่งใหม่เสมอ
- กรองลง (): วิธีการนี้จะเปรียบเทียบอ็อบเจ็กต์รากกับอ็อบเจ็กต์ลูกๆ จากนั้นจึงผลักโหนดที่ย้ายตำแหน่งไปยังตำแหน่งที่ถูกต้อง
- คัดแยก (): หากคุณใช้วิธีอาร์เรย์ในการเพิ่มองค์ประกอบใหม่ลงในอาร์เรย์ วิธี Sift-Up จะช่วยให้โหนดที่เพิ่มเข้ามาใหม่เคลื่อนไปยังตำแหน่งที่ถูกต้อง โดยจะเปรียบเทียบรายการใหม่กับรายการแม่ก่อนโดยการจำลองโครงสร้างข้อมูลแบบต้นไม้
ใช้สูตร Parent_Index = Child_Index / 2 ทำซ้ำเช่นนี้ไปเรื่อยๆ จนกว่าองค์ประกอบที่มีค่าสูงสุดจะอยู่ด้านหน้าสุดของอาร์เรย์
ฮีปพื้นฐาน Operations
ในการค้นหาค่าสูงสุดและต่ำสุดในชุดข้อมูล คุณจำเป็นต้องใช้การดำเนินการพื้นฐานเกี่ยวกับฮีป เช่น การค้นหา การแทรก และการลบ เนื่องจากองค์ประกอบต่างๆ เปลี่ยนแปลงอยู่ตลอดเวลา คุณจึงควรทราบวิธีการดังต่อไปนี้:
- หา – ค้นหารายการในฮีป
- สิ่งที่ใส่เข้าไป – เพิ่มลูกใหม่ลงในฮีป
- ลบ – ลบโหนดออกจากฮีป
สร้างฮีป
กระบวนการสร้างฮีปเรียกว่าการสร้างฮีป โดยเมื่อได้รับรายการคีย์แล้ว โปรแกรมเมอร์จะสร้างฮีปว่างเปล่า จากนั้นจึงแทรกคีย์อื่นๆ ทีละตัวโดยใช้การดำเนินการพื้นฐานของฮีป
มาเริ่มสร้าง Min-Heap โดยใช้วิธีของ William ด้วยการใส่ค่า 12, 2, 8, 1 และ 4 กัน คุณสามารถสร้างฮีปที่มี n องค์ประกอบได้โดยเริ่มจากฮีปว่างเปล่า แล้วค่อยๆ เติมองค์ประกอบอื่นๆ เข้าไปทีละน้อย โดยใช้เวลา O(n log n)
- ฮีปฟาย: รูทีนการแทรกที่ช่วยในการแทรกองค์ประกอบลงในฮีปโดยรักษาคุณสมบัติของฮีปไว้
ตัวอย่างเช่น การดำเนินการ max-heapify จะตรวจสอบว่าค่าขององค์ประกอบแม่มีค่ามากกว่าองค์ประกอบลูกหรือไม่ จากนั้นจึงสามารถเรียงลำดับองค์ประกอบโดยใช้วิธีการต่างๆ เช่น swap ได้ping.
- ผสาน: เมื่อคุณต้องการรวมฮีปสองฮีปเข้าเป็นฮีปเดียว ให้ใช้การดำเนินการผสาน (merge) เพื่อนำค่าจากทั้งสองฮีปมารวมกัน ฮีปเดิมจะยังคงอยู่
ตรวจสอบฮีป
การตรวจสอบฮีป หมายถึง การตรวจสอบจำนวนองค์ประกอบในโครงสร้างข้อมูลฮีป และตรวจสอบว่าฮีปว่างเปล่าหรือไม่
การตรวจสอบฮีปขณะจัดเรียงหรือจัดคิวองค์ประกอบนั้นมีความสำคัญ การตรวจสอบว่ามีองค์ประกอบที่จะประมวลผลโดยใช้ Is-Empty() หรือไม่นั้นสำคัญมาก ขนาดของฮีปจะช่วยในการระบุรากของ Max-Heap หรือ Min-Heap ดังนั้นคุณจึงจำเป็นต้องทราบจำนวนองค์ประกอบที่ตามหลังคุณสมบัติของฮีป
- ขนาด – ส่งคืนขนาดหรือความยาวของฮีป ซึ่งจะบอกคุณว่ามีองค์ประกอบจำนวนเท่าใดที่จัดเก็บอยู่ในลำดับที่เรียงแล้ว
- ว่างเปล่า – ส่งคืนค่า TRUE หากฮีปเป็นค่าว่าง และส่งคืนค่า FALSE หากไม่ใช่ค่าว่าง
ที่นี่ คุณกำลังพิมพ์องค์ประกอบทั้งหมดใน ลำดับความสำคัญQ วนซ้ำแล้วตรวจสอบว่า PriorityQ ไม่ว่างเปล่า
//print head the head values While (!priorityQ.isEmpty()) { System.out.print(priorityQ.poll()+" ");
การใช้โครงสร้างข้อมูลฮีป
โครงสร้างข้อมูลแบบฮีปมีประโยชน์ในแอปพลิเคชันการเขียนโปรแกรมในชีวิตจริงมากมาย เช่น:
- ช่วยในการกรองสแปม
- การนำอัลกอริทึมกราฟ เช่น Dijkstra และ Prim มาใช้
- Operaการปรับสมดุลภาระงานของระบบและการบีบอัดข้อมูล
- การหาค่าสถิติเรียงลำดับ เช่น ค่าที่เล็กที่สุดลำดับที่ k
- การนำคิวลำดับความสำคัญมาใช้ เพื่อให้สามารถค้นหารายการในลิสต์ได้ในเวลาแบบลอการิทึม
- โครงสร้างข้อมูลแบบฮีป (Heap Data Structure) ยังใช้สำหรับการเรียงลำดับโดยใช้ฮีปซอร์ต (Heap Sort) อีกด้วย
- จำลองสถานการณ์ลูกค้าที่กำลังรอคิว
- การจัดการการขัดจังหวะใน Operaระบบ ting.
- ในการเข้ารหัสแบบฮัฟฟ์แมนสำหรับการบีบอัดข้อมูล
- สนับสนุนการค้นหาแบบ best-first และฮิวริสติก A* ในการวางแผนเส้นทางด้วย AI
คุณสมบัติคิวลำดับความสำคัญฮีป
คุณสมบัติต่อไปนี้อธิบายถึงวิธีการทำงานของคิวลำดับความสำคัญที่สร้างขึ้นบนฮีป:
- ในฮีปแบบลำดับความสำคัญ ข้อมูลในรายการจะถูกเปรียบเทียบกันเพื่อพิจารณาว่าองค์ประกอบใดมีค่าเล็กกว่าหรือใหญ่กว่ากัน
- องค์ประกอบจะถูกจัดไว้ในคิวและถูกนำออกตามลำดับความสำคัญในภายหลัง
- องค์ประกอบทุกชิ้นในคิวลำดับความสำคัญจะมีหมายเลขเฉพาะที่ไม่ซ้ำกัน ซึ่งกำหนดเป็นลำดับความสำคัญ
- เมื่อออกจากคิวลำดับความสำคัญ องค์ประกอบที่มีลำดับความสำคัญสูงสุดจะออกจากคิวก่อน
ขั้นตอนการใช้งานคิวลำดับความสำคัญแบบฮีป (Heap Priority Queue) ใน Java
ส่วนถัดไปจะกล่าวถึงรายละเอียดที่เป็นรูปธรรม Java การนำไปปฏิบัติจริงเพื่อแปลงกฎเหล่านี้ให้เป็นโค้ดที่ใช้งานได้
เรียงลำดับฮีป Java สีสดสวย Code ตัวอย่าง
import java.util.Arrays; public class HeapSort { public static void main(String[] args) { int[] arr = {5, 9, 3, 1, 8, 6}; // Sort the array using heap sort heapSort(arr); // Print the sorted array System.out.println(Arrays.toString(arr)); } public static void heapSort(int[] arr) { // Convert the array into a heap for (int i = arr.length / 2 - 1; i >= 0; i--) { heapify(arr, arr.length, i); } // Extract the maximum element from the heap and place it at the end of the array for (int i = arr.length - 1; i >= 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } public static void heapify(int[] arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; // Find the largest element among the root, left child, and right child if (left < n && arr[left] > arr[largest]) { largest = left; } if (right < n && arr[right] > arr[largest]) { largest = right; } // If the largest element is not the root, swap and heapify the sub-tree if (largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); } } }
เอาท์พุต
Original Array: 5 9 3 1 8 6 Heap after insertion: 9 8 6 1 5 3 Heap after sorting: 1 3 5 6 8 9
เรียงลำดับฮีป Python สีสดสวย Code ตัวอย่าง
def heap_sort(arr): """ Sorts an array in ascending order using heap sort algorithm. Parameters: arr (list): The array to be sorted. Returns: list: The sorted array. """ n = len(arr) # Build a max heap from the array for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # Extract elements from the heap one by one for i in range(n - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0] # swap the root with the last element heapify(arr, i, 0) # heapify the reduced heap return arr def heapify(arr, n, i): """ Heapifies a subtree with the root at index i in the given array. Parameters: arr (list): The array containing the subtree to be heapified. n (int): The size of the subtree. i (int): The root index of the subtree. """ largest = i # initialize largest as the root left = 2 * i + 1 # left child index right = 2 * i + 2 # right child index # If left child is larger than root if left < n and arr[left] > arr[largest]: largest = left # If right child is larger than largest so far if right < n and arr[right] > arr[largest]: largest = right # If largest is not root if largest != i: arr[i], arr[largest] = ( arr[largest], arr[i], ) # swap the root with the largest element heapify(arr, n, largest) # recursively heapify the affected subtree arr = [4, 1, 3, 9, 7] sorted_arr = heap_sort(arr) print(sorted_arr)
เอาท์พุต
[1, 3, 4, 7, 9]
ต่อไป คุณจะได้เรียนรู้เกี่ยวกับ วิธีการแบ่งส่วน.
