Cara menggunakan php heap
Seperti yang Anda ketahui, heapsort juga merupakan salah satu algoritma pengurutan yang paling banyak ditanyakan selain mergesort dan quicksort dan hari ini kita akan membicarakannya dan saya akan mencoba yang terbaik untuk menjelaskannya dalam istilah yang lebih sederhana seperti untuk pemula. cukup rumit lebih jadi jika seseorang memiliki sedikit pengetahuan tentang tumpukan. Tapi jangan takut aku mendukungmu. Jadi sekarang mari kita masuk ke dalamnya. Sebelum beralih ke heap sort, Anda perlu mengetahui tentang terminologi berikut untuk memahami cara kerja heapsort dengan benar. Jadi mari kita mulai dengan menjelaskan istilah-istilah yang disebutkan di atas Heapify adalah proses** untuk membuat struktur data heap dari pohon biner. **Sekarang Heapify adalah operasi terpenting pada struktur data heap karena membantu mempertahankan struktur heap setelah beberapa operasi dilakukan pada heap seperti (penyisipan, penghapusan). Kami akan sering menggunakan operasi ini dan itu akan berguna saat merancang heap sort. kerja
heapify ditunjukkan di bawah ini Array masukan 2. Ubah array ini menjadi pohon biner lengkap. Pohon biner lengkap dibuat dari array 3. Buat tumpukan dari pohon biner.
Setelah Heapify, tumpukan maksimal dibuat Sekarang setelah kita mempelajari semua istilah penting, mari kita mulai membuat algoritme pengurutan tumpukan.
#sorting #sorting-algorithms #heap #heapsort #sort medium.comSeperti yang Anda ketahui, heapsort juga merupakan salah satu algoritme pengurutan yang paling banyak ditanyakan selain mergesort dan quicksort dan hari ini kita akan membahasnya. In this article we'll explore the world of Heaps, the data structure. Because some knowledge of Trees is useful I highly suggest you read my Trees and Tree Traversal in PHP article before diving into this one.
What is a Heap?A Heap is a data structure. So it is a way of how data is organized and how it can be accessed in an efficient way. There are many types of data structures, like: (Doubly) Linked Lists, Graphs, Stacks, Queues, Arrays and HashMaps. Each of these data types can be used for various use cases; but some are more performant than others in certain situations. 🎄 A Heap is a Binary TreeThe data structure of a Heap is a Binary Tree. Starting with a Root-node, every node has a maximum of two children; left & right. But there are two rules these trees have to follow. Heap rule #1: The parent node has a lower value (MinHeap) or a higher value (MaxHeap) than its childrenThere are two types of heaps: a MinHeap and a MaxHeap. The difference between these are the order in which the nodes are placed inside the Tree. The children of a node in a MinHeap have a higher value then their parent, while the children of a node in a MaxHeap will have a lower value then their parent. If there are two identical values, a node can have a child with the same value. This behavior flows all the way down the Tree.
Heap rule #2: A Heap is a Complete Binary TreeThere are 5 types of Binary Trees:
So in a Complete Binary Tree, and thus also a Heap, it is not possible to have a node with only a right child-node. But it ís possible to have one with only a left child node. 🔨 Creating a HeapEnough theory; let's look at an example of a Heap.
Let's say we have a list of values. I'll put it in a PHP array to make it look pretty:
We'll make this list into a MaxHeap. Remember; in this case the highest
value goes at the Root-node, making the values decrease every level of the tree. So in this case our Root-node will be This root-node will have two children. Those values will be Both of these values can have 2 children; so lets find the next 4 values in declining order from the list: And our final remaining number So this is the MaxHeap we created:
At this point you might be thinking: this feels like cheating. And yes, I know; we cheated a bit by sorting the integers in our head from largest to smallest first, and then filling out the Heap from left to right. But that is actually the fastest way of creating a MaxHeap. However, what if we didn't know the values up front, or if they came in a random order? How would we fill out this MaxHeap? Adding values to an empty HeapSo now let's create a Heap without sorting the numbers beforehand. In this case it would be a more iterative process:
After this we go back to step 2 and insert the next value:
The next value to add will be Boring! - Ok, let's stop this explanation here. I think you get the point. If you really want a more in-depth visualization; I've added some useful links at the end of this article including a video explanation. Extracting a value from a HeapWe've seen how you can add a value to the Heap By injecting it, and then sifting it up. But how can you extract a value? It isn't as simple as removing the node, because that might cut the Tree in half. Take the Root-node for instance. On a Heap it's very likely you want to extract that value. But simply removing it will create two new Trees. To avoid this Tree splitting, we need to replace (or swap) the Root-node with the last node. In a heap the last node can always be removed from a Tree, without corrupting it, because the Tree is already sorted. However, when we swap the Root-node with the last node, and extract it, the Tree will no longer be a Heap at that point, because the wrong value will be at the top. So we need to turn this Tree into a Heap again, starting with the Root-node. This process is not as lengthy as turning an entire unsorted Tree into a Heap, because most of the Tree is already in the correct order.
Instead of sifting the Root-node up, we need to sift the Root-node down. In this case we need to compare the node to both its children, and swap it with the largest of the two. And keep repeating it, until the node is in its correct position. At this point the Tree is once again a Heap. Creating a Heap in PHPCreating a Heap is made easy in PHP by using the
And then there is also PHP also provides a
Knowing all this we can create a MaxHeap from our
We saw that
Creating a custom MaxHeap in PHPWhen using a MaxHeap to sort a list of objects it is possible the value of those objects is calculated through a function. In
that case the regular Imagine having a shop with product represented by a
In this example we convert the weight amount of pounds into grams in order to compare the values accordingly.
Array Index Algorithm for HeapsRemember how Heaps are Complete Binary Trees? This is actually a very helpful characteristic of a Heap. If we give every node in the tree a 0-based index key, and moved from top to bottom, left to right, we can actually quite simply figure out what the keys of the children of a specific node are. So we can store a heap as an array.
Assuming Let's try that out. We want the values for the left and right child of
We can also do the reverse and find out the parent of the current node. The algorithm for that is: Heapify an 0-based arrayBecause a Complete Binary Tree can be stored as a 0-based array; we can also see any 0-based array as a Complete Binary Tree. How is this helpful? Because it's very easy and efficient to turn any existing Complete Binary Tree into a Heap. When we want to convert a Complete Binary Tree into a Heap, we only have to sort half of it. Because the sorting is done by swapping two nodes, the other half of the Tree will automatically also end up in their correct position.
You can try this out yourself:
If done correctly, you end up with a Tree like this:
As you can see, by only sifting down half the array, the other half of the Heap automatically ended up in a correct position. 🤷 When are Heaps useful?Because there are many types of data structures, there are also many ways to solve a problem. Sometimes a simple array is all you need. But Heaps have their time to shine. Direct access to the highest (or lowest) valueA MaxHeap (or MinHeap) has direct access to the highest (or lowest) value of the dataset. So whenever you are working with large datasets for which you need the maximum (or minimum) value; a Heap is a safe bet. As you've seen we only need to sort half the dataset in order to figure out the minimum or maximum value. Which is pretty fast. Working with a lot of inserts and removalsWhen inserting a new value into a dataset, a Heap is more efficient because it only performs (relatively) a few comparisons to end up in the right spot. In the worst case scenario an array would need to perform a comparison for every value it has. Because a Heap is a binary tree, the worst case would need exponentially fewer comparisons. Making it a more efficient. Sorting arraysAn array can be sorted by using a MaxHeap in a process known as HeapSort. Because a MaxHeap continuously has the highest value at the top, you can extract that value and place it at it to the beginning of an array. By adding the next value, and the next, and the next, at the beginning of the array, it ends up sorted from lowest to highest.
Priority QueuesWhile also a topic for a future blog post, queues are essentially a First-In First-Out system that adds new values at the end of a list, and extracts values from the start of the list. A variant on this is where you use a MaxHeap that contains a
Because this is such a frequently used case for MaxHeaps, PHP actually provides a Instead of updating your object to contain a priority, you can insert the object with a priority.
And because we only need to partially sort a Heap find the highest priority, this too is a lot more efficient that sorting an array-queue after every insertion. Real world exampleA very nice real world example of a Heap implemented with a PHP array can be found in the In this example they implemented a queue of callbacks based on an expiry time. Whenever the expiry time has passed, the callback will be extracted. So this is an example of a Priority Queue, but it's based on a MinHeap instead of a MaxHeap; because the lowest expiry time has to be on top. Alternative for the Standard PHP Library (SPL)As u/sproingie pointed out on Reddit The SPL data structures are not
great. They are a great jumping of point in getting started with other data structures. But if you want / need more performance you could install the Data Structures extension. While it has a Priority Queue, there is no generic Heap implementation. But you might be able to build this yourself using the 🔗 Useful links
Thanks for readingLike I stated at the beginning of the post; Trees and Heaps are very visual things and not everything is as easily explained with a bunch of text. I do hope after reading this post you understand the gist of it. If you have any questions please leave a comment. I hope you enjoyed reading this article! If so, please leave a 👍 reaction or a 💬 comment and consider subscribing to my newsletter! I write posts on PHP almost every week. You can also follow me on 🐦 twitter for more content and the occasional tip. |