What is the use of a heap data structure?

Question

I am working on homework with Heaps, and I understand how they are structured. The heap must have every node satisfying the heap property,

The max-heap property is that for each node I am different than the root, Heap [Parent (i)]> Heap [i]

So, with each node, higher nodes have higher numbers, lower nodes have lower numbers. I understand it. But I cannot see the use of the heap, and then just get the highest n numbers in the list. I do not see an easy way to search for a specific value and return node, or to search for n the smallest numbers (in the max heap). Both are relatively simple in the binary search tree.

Why don't you just use a simple binary search tree? Or better yet, a balanced binary search tree?

EDIT: I must point out that this is not a search for an answer to a home problem. The problem with homework was writing pseudo-code for the parallel p-heap for the insert () and extractMax () functions. And I already answered them. They just made me realize that I really didn't understand Haps.

Answer 1

Due to the lack of pointers (heaps usually use an array-based data structure), operations are generally faster than for a binary tree. In addition, some more complex heaps (e.g. binomial) can be effectively combined, which is not easy to do for a binary tree. There is also information on this SO issue .

Answer 2

The heap data structure has many applications.

• Heapsort . One of the best sorting methods in place and without quadratic worst case scenarios.
• Selection algorithms . The search for the minimum and maximum values ​​of both the minimum and maximum, median or even the kth element itself can be performed in linear (often constant) time using heaps. [ 4]
• Graph Algorithms . Using heaps as internal bypass data structures, runtime is reduced in polynomial order. Examples of such problems are the minimal pairing algorithm of the Prim tree and the Dijkstra shortest path algorithm.

Full and almost complete binary heaps can be represented in a very economical way using only an array. The first (or last) element will contain the root. The following two elements of the array contain its children. The next four contain four children of two child nodes, etc. Thus, the children of the node at position n will be at positions 2n and 2n + 1 in the array based on one or 2n + 1 and 2n + 2 in the array with a zero value. This allows you to move up or down the tree, performing simple index calculations. Heap balancing is done by replacing items that are out of order. Since we can build a bunch from an array without requiring additional memory (for example, for nodes), heapsort can be used to sort the array in place.

Another advantage of heaps over trees in some applications is that heaps can be built in linear time using the Taryan algorithm.

Link: http://en.wikipedia.org/wiki/Heap_%28data_structure%29