โครงสร้างข้อมูลฮีป: ฮีปคืออะไร ฮีปต่ำสุดและสูงสุด (ตัวอย่าง)

ฮีปคืออะไร?

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

ทำไมคุณถึงต้องการโครงสร้างข้อมูลฮีป?

ต่อไปนี้เป็นเหตุผลหลักในการใช้โครงสร้างข้อมูลฮีป:

โครงสร้างข้อมูลฮีปอนุญาตให้ลบและแทรกในเวลาลอการิทึม – O(log₂น)
ข้อมูลในแผนผังได้รับการออกแบบตามลำดับเฉพาะ นอกเหนือจากการอัปเดตหรือสอบถามสิ่งต่างๆ เช่น ค่าสูงสุดหรือต่ำสุดแล้ว โปรแกรมเมอร์ยังสามารถค้นหาความสัมพันธ์ระหว่างผู้ปกครองและลูกหลานได้
คุณสามารถนำแนวคิดของการ โมเดลวัตถุเอกสาร เพื่อช่วยคุณในการทำความเข้าใจโครงสร้างข้อมูลฮีป

ประเภทของฮีป

โครงสร้างข้อมูลฮีปมีอัลกอริทึมต่างๆ สำหรับการจัดการการแทรกและการลบองค์ประกอบในโครงสร้างข้อมูลฮีป รวมถึง Priority-Queue, Binary-Heap, Binomial Heap และ ฮีปเรียงลำดับ.

ลำดับความสำคัญ-คิว: มันเป็นโครงสร้างข้อมูลนามธรรมที่มีวัตถุที่จัดลำดับความสำคัญ แต่ละรายการหรือวัตถุแต่ละรายการจะมีการจัดลำดับความสำคัญไว้ล่วงหน้า ดังนั้นวัตถุหรือรายการที่ได้รับมอบหมายให้มีลำดับความสำคัญสูงกว่าจะได้รับบริการก่อนส่วนที่เหลือ
ไบนารีฮีป: ไบนารีฮีปเหมาะสำหรับการดำเนินการฮีปแบบง่ายๆ เช่น การลบและการแทรก
ทวินามฮีป: ฮีปทวินามประกอบด้วยชุดของต้นไม้ทวินามที่ประกอบเป็นฮีป ต้นไม้ Binomial Heap ไม่ใช่ต้นไม้ธรรมดาเนื่องจากมีการกำหนดไว้อย่างเคร่งครัด จำนวนองค์ประกอบทั้งหมดในต้นไม้ทวินามจะมี 2 เสมอⁿ โหนด
ฮีปเรียงลำดับ: ต่างจากอัลกอริทึมการเรียงลำดับส่วนใหญ่ อัลกอริทึมการเรียงลำดับแบบฮีปใช้พื้นที่ O(1) สำหรับการดำเนินการเรียงลำดับ อัลกอริทึมการเรียงลำดับนี้ใช้การเปรียบเทียบ โดยที่การเรียงลำดับจะเกิดขึ้นตามลำดับที่เพิ่มขึ้นโดยเปลี่ยนเป็นฮีปสูงสุดก่อน คุณสามารถมองฮีปเป็นทรีค้นหาแบบไบนารีที่มีคุณภาพที่ได้รับการอัปเกรด

โดยทั่วไป โครงสร้างข้อมูลฮีปจะใช้สองกลยุทธ์ สำหรับอินพุต 12 – 8 – 4 – 2 และ 1

Min Heap – ค่าน้อยที่สุดที่ด้านบน
Max Heap – ค่าสูงสุดที่ด้านบน

มินฮีป

ในโครงสร้าง Min Heap โหนดรูทมีค่าเท่ากับหรือเล็กกว่ารายการลูกบนโหนดนั้น โหนดฮีปของ Min Heap นี้มีค่าต่ำสุด โดยรวมแล้ว โครงสร้าง min-heap นั้นเสร็จสมบูรณ์แล้ว ต้นไม้ไบนารี.

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

ตัวอย่างมินฮีป

ในไดอะแกรมด้านบน คุณสามารถสังเกตเห็นลำดับที่ชัดเจนตั้งแต่รูทจนถึงโหนดต่ำสุด

สมมติว่าคุณเก็บองค์ประกอบไว้ในอาร์เรย์ Array_N[12,2,8,1,4] ดังที่คุณเห็นได้จากอาร์เรย์ องค์ประกอบรากกำลังละเมิดลำดับความสำคัญของ Min Heap เพื่อรักษาคุณสมบัติ Min Heap คุณต้องดำเนินการ min-heapify เพื่อสลับองค์ประกอบจนกว่าจะตรงตามคุณสมบัติ Min Heap

แม็กซ์ฮีป

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

ต่อไปนี้เป็นวิธีการบางส่วนในการใช้งาน Java Max Heap

เพิ่ม (): วางองค์ประกอบใหม่ลงในฮีป หากคุณใช้อาร์เรย์ วัตถุจะถูกเพิ่มที่ส่วนท้ายของอาร์เรย์ ในขณะที่อยู่ในแผนผังไบนารี วัตถุจะถูกเพิ่มจากบนลงล่าง และต่อจากซ้ายไปขวา
ลบ (): วิธีการนี้ช่วยให้คุณสามารถลบองค์ประกอบแรกออกจากรายการอาร์เรย์ได้ เนื่องจากองค์ประกอบที่เพิ่มใหม่ไม่ใหญ่ที่สุดอีกต่อไป วิธี Sift-Down จะผลักองค์ประกอบนั้นไปยังตำแหน่งใหม่เสมอ
ร่อนลง ():วิธีการนี้จะเปรียบเทียบวัตถุรากกับวัตถุย่อย จากนั้นจึงผลักโหนดที่เพิ่มใหม่ไปยังตำแหน่งที่ถูกต้อง
ร่อนขึ้น (): หากคุณใช้วิธีการอาร์เรย์เพื่อเพิ่มองค์ประกอบที่แทรกใหม่ลงในอาร์เรย์ วิธีการ Sift-Up จะช่วยให้โหนดที่เพิ่มใหม่ย้ายตำแหน่งไปยังตำแหน่งใหม่ รายการที่แทรกใหม่จะถูกเปรียบเทียบกับรายการหลักก่อนโดยการจำลองโครงสร้างข้อมูลแบบต้นไม้
ใช้สูตร Parent_Index=Child_Index/2 คุณทำสิ่งนี้ต่อไปจนกว่าองค์ประกอบสูงสุดจะอยู่ด้านหน้าอาร์เรย์

ฮีปพื้นฐาน Operations

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

หา – ค้นหารายการในฮีป
สิ่งที่ใส่เข้าไป – เพิ่มลูกใหม่ลงในฮีป
ลบ – ลบโหนดออกจากฮีป

สร้างฮีป

กระบวนการสร้างฮีปเรียกว่าการสร้างฮีป เมื่อได้รับรายการคีย์ โปรแกรมเมอร์จะสร้างฮีปเปล่า จากนั้นแทรกคีย์อื่นๆ ทีละรายการโดยใช้การดำเนินการฮีปพื้นฐาน

ดังนั้นเรามาเริ่มสร้าง Min-heap โดยใช้วิธีของ Willaim โดยการใส่ค่า 12,2,8,1 และ 4 ลงในฮีป คุณสามารถสร้างฮีปด้วยองค์ประกอบ n ตัวโดยเริ่มจากฮีปว่าง จากนั้นเติมองค์ประกอบอื่นๆ ตามลำดับโดยใช้เวลา O (nlogn)

Heapify: ในอัลกอริทึมการแทรกซึ่งช่วยแทรกองค์ประกอบเข้าไปในฮีป ตรวจสอบว่าโครงสร้างข้อมูลของฮีปมีคุณสมบัติที่เน้นไว้หรือไม่
ตัวอย่างเช่น การกำหนด heapify สูงสุดจะตรวจสอบว่าค่าของ parent มากกว่าค่าของ element ย่อยหรือไม่ จากนั้นสามารถเรียงลำดับองค์ประกอบได้โดยใช้เมธอดเช่น swapping

ผสาน: เมื่อพิจารณาว่าคุณมีสองฮีปที่จะรวมเป็นอันเดียว ให้ใช้ฮีปผสานเพื่อนำค่าจากทั้งสองฮีปมารวมกัน แต่ฮีปเดิมยังคงอยู่

ตรวจสอบฮีป

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

การตรวจสอบฮีปนั้นมีความสำคัญในฐานะการเรียงลำดับหรือการจัดคิวองค์ประกอบ การตรวจสอบว่าคุณมีองค์ประกอบที่ต้องประมวลผลโดยใช้ Is-Empty() นั้นมีความสำคัญ ขนาดของฮีปจะช่วยระบุตำแหน่งของฮีปสูงสุดหรือฮีปต่ำสุด ดังนั้น คุณจึงต้องทราบองค์ประกอบที่ตามหลังคุณสมบัติฮีป

ขนาด – ส่งกลับขนาดหรือความยาวของฮีป คุณสามารถบอกได้ว่ามีองค์ประกอบกี่รายการเรียงตามลำดับ
มันว่างเปล่า – ถ้าฮีปเป็นค่า NULL มันจะส่งคืนค่า TRUE หากไม่ใช่มันจะส่งคืนค่า FALSE

ที่นี่ คุณกำลังพิมพ์องค์ประกอบทั้งหมดใน ลำดับความสำคัญQ วนซ้ำแล้วตรวจสอบว่า PriorityQ ไม่ว่างเปล่า

//print head the head values
       While (!priorityQ.isEmpty()) {
        System.out.print(priorityQ.poll()+" ");

การใช้โครงสร้างข้อมูลฮีป

โครงสร้างข้อมูลฮีปมีประโยชน์ในแอปพลิเคชันการเขียนโปรแกรมจำนวนมากในชีวิตจริง เช่น:

ช่วยในการกรองสแปม
การนำอัลกอริธึมกราฟไปใช้
Operaปรับสมดุลโหลดของระบบ และการบีบอัดข้อมูล
ค้นหาลำดับในสถิติ
ใช้ลำดับความสำคัญซึ่งคุณสามารถค้นหารายการในรายการในเวลาลอการิทึม
โครงสร้างข้อมูลฮีปยังใช้สำหรับการเรียงลำดับด้วย
จำลองลูกค้าในบรรทัด
ขัดจังหวะการจัดการใน Operaระบบ ting.
ในการเข้ารหัสของ Huffman สำหรับการบีบอัดข้อมูล

คุณสมบัติคิวลำดับความสำคัญฮีป

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

ขั้นตอนในการใช้ฮีป Priority Queue ใน Java

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

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 the root and the largest element 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 พร้อมตัวอย่างโค้ด

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)