PHP Master | Data Structures for PHP Devs: Heaps

This article introduces heaps, a specialized tree-like data structure closely related to stacks, queues, and trees. Heaps maintain the heap property: a parent node's value is always ordered relative to its children's values. Key concepts include max-heaps, min-heaps, and priority queues.

Key Takeaways:

• Heaps are tree-like structures adhering to the heap property. Variations include max-heaps (parent ≥ children), min-heaps (parent ≤ children), and priority queues.
• Typically implemented as complete binary trees, heaps lack sibling or cousin ordering, unlike binary trees. Common operations: create, isEmpty, insert, extract.
• Array-based heap implementation is feasible. A binary heap with n nodes has at most 2n 1 nodes. Insertion reverses the extraction process.
• PHP offers SplHeap, SplMaxHeap, SplMinHeap, and SplPriorityQueue for heap management. Priority queues, often heap-based, find use in service desks and graph algorithms.

Heaps in Detail:

Max-heaps place the largest value at the root, with parents always larger than or equal to their children. Min-heaps are the inverse. PHP's SPL provides tools for all these types. A max-heap example:

Heaps, while often binary trees, lack the inherent ordering of binary trees. Basic operations include: create, isEmpty, insert, and extract (removing the root). Extracting the root from a heap leaves a semiheap, requiring restructuring. This is done by moving the last node to the root and then "trickling down" the new root until the heap property is restored.

Array-Based Heap Implementation:

A binary max-heap can be implemented using an array. The following PHP code demonstrates this:

<?php
class BinaryHeap {
    protected $heap;
    // ... (rest of the code as provided in the input) ...
}
?>

Insertion adds an item to the end and "trickles it up" to its correct position. Extraction removes the root, replaces it with the last item, and "trickles it down."

SplMaxHeap and SplMinHeap:

PHP's SplMaxHeap and SplMinHeap simplify heap management. Extend these classes and override the compare method for custom comparisons.

SplPriorityQueue:

SplPriorityQueue acts like a queue but uses a max-heap internally. It's useful for priority-based tasks. Override the compare method to define priority ordering. Example:

<?php
class PriQueue extends SplPriorityQueue {
    public function compare($p1, $p2) {
        // ... (comparator logic) ...
    }
}
?>

Summary:

This article covered the heap data structure, its implementation in PHP (both manually and using SPL classes), and its applications, particularly in priority queues. Future articles will explore graphs.

Frequently Asked Questions (FAQ):

The provided FAQ section is comprehensive and accurately addresses common questions about heaps in PHP. There is no need for modification or addition.

The above is the detailed content of PHP Master | Data Structures for PHP Devs: Heaps. For more information, please follow other related articles on the PHP Chinese website!