# Heap Datastructures- Detailed Explanation in Python.

What are heap data structures?

When a binary tree is complete, it is a special binary tree where every parent node has a value lesser than or equal to any of its children.

This implementation uses an array for which, `heap[k] <= heap[2*k+1]`

and `heap[k] <= heap[2*k+2]`

for all *k*, counting elements from zero

The smallest element in a heap is always the root.(heap[0])

There are two types of the heap, Max-Heap and Min Heap.

In a ** Max-Heap** the key present at the root node must be greatest among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree.

In a ** Min-Heap** the key present at the root node must be minimum among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree.

*How will you find the height of a heap?*

Let the size of heap be **N** and height be **h**

If we take few examples, we can actually make a note that the value of h in a heap(complete Binary Tree) is **ceil(log2(N+1)) — 1.**

*Heap Functions*

*Heap Functions*

*To create a heap, use a list initialized to **[]**, or you can transform a populated list into a heap via function heapify()*

The following functions are provided:

**heapq.heappush**

**(***heap*, *item*)

**heapq.heappush**

*heap*,

*item*)

Push the item as value to the heap.

**heapq.heappop**

**(***heap*)

**heapq.heappop**

*heap*)

Pop and return the smallest item from the *heap*, maintaining the heap invariant. If the heap is empty, `IndexError`

is raised. To access the smallest item without popping it, use `heap[0]`

.

`heapq.`**heappushpop**

(*heap*, *item*)

**heappushpop**

Push *item* on the heap, then pop and return the smallest item from the *heap*. The combined action runs more efficiently than `heappush()`

followed by a separate call to `heappop()`

.

`heapq.`**heapify**

(*x*)

**heapify**

Transform list *x* into a heap, in-place, in linear time.

`heapq.`**heapreplace**

(*heap*, *item*)

**heapreplace**

Pop and return the smallest item from the *heap*, and also push the new *item*. The heap size doesn’t change. If the heap is empty, `IndexError`

is raised.

`heapq.`**merge**

(**iterable*, *key=None*, *reverse=False*)

**merge**

Merge multiple sorted inputs into a single sorted output (for example, merge timestamped entries from multiple log files). Returns the iterator over the values.

`heapq.`**nlargest**

(*n*, *iterable*, *key=None*)

**nlargest**

Return a list with the *n* largest elements from the dataset defined by *iterable*. *key*, if provided, specifies a function of one argument that is used to extract a comparison key from each element in *iterable* (for example, `key=str.lower`

). Equivalent to: `sorted(iterable, key=key, reverse=True)[:n]`

.

`heapq.`**nsmallest**

(*n*, *iterable*, *key=None*)

**nsmallest**

Return a list with the *n* smallest elements from the dataset defined by *iterable*. *key*, if provided, specifies a function of one argument that is used to extract a comparison key from each element in *iterable* (for example, `key=str.lower`

).

Implementation of Heapsort using Heapq Datastructre by pushing all values onto a heap and then popping off the smallest values one at a time.

Next Article, we will discuss Priority Queues