# Heap Data Structure Assignment Help And Online Tutoring

## Heap Data Structure

A heap is a specialized tree -based data structure that satisfies the heap property: if B is a child node of A, then key(A) = key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min-heap.) There is no restriction as to how many children each node has in a heap, although in practice each node has at most two. The heap is one maximally-efficient implementation of an abstract data type called a priority queue. Heaps are crucial in several efficient graph algorithms such as Dijkstr’s algorithm, and in the sorting algorithm heapsort.

Example of a complete binary max-heap

Heaps are based on the notion of a complete tree, for which we gave an informal definition early.

Formally:

A binary tree is completely full if it is of height, h, and has 2h+1-1 nodes.

A binary height of height, h, is complete if

1. it is empty or
2. its left subtree is complete of height h-1 and its right subtree is completely full of height h-2 or
3. its left subtree is completely full of height h-1 and its right subtree is complete of height h-1.

A complete tree is filled from the left:

1. all the leaves are on
• the same level or