Menu
I felt that they are very similar to each other, except at some concepts. In external sorting their functions are basically the same, that is to find the minimal/maximal value in k runs. So are there some significant differences between them two ?
906
Heap takes less time complexity as compared to the sorted arrays in terms of creation. Building heap takes O(n) time complexity, whereas building Sorted Array takes O(n. log n) time. Insertion and deletion in the heaps are efficient heaps as compared to sorted arrays.
A heap is a binary tree inside an array, so it does not use parent/child pointers. A heap is sorted based on the "heap property" that determines the order of the nodes in the tree. Common uses for heap: To build priority queues.
A heap is a complete binary tree. A max-heap is a complete binary tree in which the value in each internal node is greater than or equal to the values in the children of that node. A min-heap is defined similarly.
In a heap, the highest (or lowest) priority element is always stored at the root. However, a heap is not a sorted structure; it can be regarded as being partially ordered.
For the most part, loser trees and heaps are quite similar. However, there are a few important distinctions. The loser tree, because it provides the loser of each match, will contain repeat nodes. Since the heap is a data-storing structure, it won't contain these redundancies. Another difference between the two is that the loser tree must be a full binary tree (because it is a type of tournament tree), but the heap does not necessarily have to be binary.
Finally, to understand a specific quality of the loser tree, consider the following problem: Suppose we have k sequences, each of which is sorted in nondecreasing order, that are to be merged into one sequence in nondecreasing order. This can be achieved by repeatedly transferring the element with the smallest key to an output array. The smallest key has to be found from the leading elements in the k sequences. Ordinarily, this would require k − 1 comparisons for each element transferred. However, with a loser tree, this can be reduced to log2 k comparisons per element.
Source: Handbook of Data Structures and Applications, Dinesh Mehta
166
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
