# Introduction to the Heap Data Structure – DZone

Data structures are essential for computer science, as they provide a way to organize and store data efficiently. A heap data structure is a tree-based data structure that is widely used in computer science for its efficiency and versatility. In this article, we will explore the heap data structure in depth, including its properties, types, and applications.

## Properties of Heap Data Structure

A heap data structure is a complete binary tree that satisfies the heap property. The heap property is that for every node in the heap, the key of the parent node is either greater than or equal to (in a max heap) or less than or equal to (in a min-heap) the keys of its children. This property ensures that the maximum (in a max heap) or minimum (in a min-heap) element is always at the root of the tree.

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.

A heap data structure can be implemented as an array, where the left child of a node at index i is located at index 2i+1, and the right child is located at index 2i+2. Similarly, the parent of a node at index j is located at index (j-1)/2.

## Types of Heap Data Structure

There are two types of heap data structures: max heap and min heap.

### 1. Max Heap

In a max heap, the root node has the maximum key. The keys of all nodes in the heap are less than or equal to the key of the root node. This means that the maximum element in the heap can be found at the root of the heap. In a max heap, the children of a node always have smaller keys than the parent.

### 2. Min Heap

In a min heap, the root node has the minimum key. The keys of all nodes in the heap are greater than or equal to the key of the root node. This means that the minimum element in the heap can be found at the root of the heap. In a min heap, the children of a node always have greater keys than the parent.

## Applications of Heap Data Structure

The heap data structure has many applications in computer science, including sorting algorithms, priority queues, and graph algorithms.

### Sorting Algorithms

The heap data structure is used in sorting algorithms, such as heapsort. In heapsort, the input array is first transformed into a max heap. The maximum element is then swapped with the last element of the heap, which is removed from the heap. The heap property is then restored by heapifying the remaining elements. This process is repeated until all elements have been removed from the heap. The result is a sorted array.

### Priority Queues

The heap data structure is used in priority queues, which are used to manage a set of elements with associated priorities. Priority queues are commonly used in computer science for scheduling, task management, and other applications where elements need to be processed in order of priority.

In a priority queue, the highest priority element is dequeued first. A max heap is used to implement a priority queue, where the highest priority element is stored at the root of the heap. The priority queue operations of enqueue (inserting an element into the queue) and dequeue (removing the highest priority element from the queue) can be implemented efficiently using the heap data structure.

### Graph Algorithms

The heap data structure is used in graph algorithms, such as Dijkstra’s shortest path algorithm and Prim’s minimum spanning tree algorithm. In Dijkstra’s algorithm, a priority queue is used to store the vertices that have not been processed yet, with the highest priority given to the vertex with the shortest distance from the source vertex. The priority queue is implemented using a min heap, where the vertex with the shortest distance from the source vertex is stored at the root of the heap. In each iteration of the algorithm, the vertex with the shortest distance is dequeued from the priority queue, and its adjacent vertices are updated with their distances from the source vertex.

In Prim’s algorithm, a priority queue is used to store the edges that connect the explored and unexplored vertices, with the highest priority given to the edge with the smallest weight. The priority queue is implemented using a min heap, where the edge with the smallest weight is stored at the root of the heap. In each iteration of the algorithm, the edge with the smallest weight is dequeued from the priority queue, and the vertices connected by the edge are added to the explored vertices set.

## Implementation of Heap Data Structure

The heap data structure can be implemented using an array or a tree data structure. In array implementation, the elements of the heap are stored in an array, with the root node at index 0. The left child of a node at index i is located at index 2i+1, and the right child is located at index 2i+2. The parent of a node at index j is located at index (j-1)/2. The heap property is maintained by performing heapify operations on the elements of the heap.

In tree implementation, the heap is implemented as a binary tree data structure, with the root node at the top of the tree. The left child of a node is located to the left of the parent node, and the right child is located to the right of the parent node. The heap property is maintained by performing heapify operations on the nodes of the heap.

## Heapify Operation

The heapify operation is used to maintain the heap property of the heap data structure. The heapify operation transforms the subtree rooted at a node into a heap. A heapify operation is performed on a node when the heap property of the heap is violated due to an insertion or deletion operation.

In max heap, heapify operation is performed by comparing the key of the parent node with the keys of its children. If the key of the parent node is less than the key of one of its children, the keys are swapped. The heapify operation is then performed recursively on the child node that has been swapped.

In min heap, heapify operation is performed by comparing the key of the parent node with the keys of its children. If the key of the parent node is greater than the key of one of its children, the keys are swapped. The heapify operation is then performed recursively on the child node that has been swapped.

## Complexity of Heap Data Structure

The time complexity of heap data structure operations depends on the height of the heap, which is logarithmic in the number of elements in the heap. The space complexity of heap data structure is linear in the number of elements in the heap.

The time complexity of building a heap from an array of n elements is O(n), using the bottom-up heap construction algorithm. The time complexity of inserting an element into a heap is O(log n), as it requires one heapify operation. The time complexity of deleting the root node of a heap is O(log n), as it requires one heapify operation. The time complexity of finding the maximum or minimum element of a heap is O(1), as it is located at the root of the heap.