CODEWITHSUNDEEP
data-structuresheap
user5595273
user5595273

Reputation:

What is the correct definition of a heap

I was reading about heaps in Java programming. In my textbook, I found this definition of a heap: a heap is a complete binary tree with the following properties: 1) the value in the root is the smallest item in the tree; 2) every subtree is a heap

But when I was watching videos about heaps, I found a totally different definition of heaps which says: In a heap the parent keys are bigger then the children.

Now I am confused because the two definitions do not fit with each other. Which definition is the correct one?

Thanks!

Upvotes: 0

Views: 513

Answers (2)

YoungHobbit
YoungHobbit

Reputation: 13402

Both the definition are correct.

There are two types of Heap.

Min Heap: In which parent node is always smaller than its children.

Max Heap: In which, parent node is always larger than its children.

This smaller/larger value of the parent than it's children is called Heap Property. This Heap Property has be satisfied by each node of the tree.

The complexity of constructing the Heap from a given array is O(n). This operation is called Heapify.

Given a Heap, adding/removing a node/element from the Heap. The complexity of the operation is O(log(n)).

The complexity of the Sorting any array using the Heap data structure (Heap Sort) is O(n.log(n)). Basically you extract the top (root) element from the Min Heap. This operation is repeated n times, So complexity is O(n.log(n))

Upvotes: 2

Baklap4
Baklap4

Reputation: 4202

Quoting wikipedia here

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap. A heap can be classified further as either a "max heap" or a "min heap". In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node. Heaps are crucial in several efficient graph algorithms such as Dijkstra's algorithm, and in the sorting algorithm heapsort. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree (see figure).

There are 2 types of heaps:

Min Heap: Parent node is always smaller than the childeren.

Max Heap: Parent node is always larger than the childeren.

Upvotes: 0

Related Questions