A heap is a data structure in the form of a balanced binary tree with a special constraint that will be introduced in the followings. In the tree, each node contains a key and two references to two child nodes. The key represents a value, which is normally an integer since every data type in the computer systems can be converted into integer type. Each reference is an address that enable us to retrieve each child node. For example, in C, the reference is declared as a pointer and stores the address of a child node.

2 Types of Heaps

There are two types of heap: max-heaps and min-heaps. They are classified the following special constraint.

A?max-heap is a balanced binary tree such that the key of each node no less than the key of its child nodes, which is denoted by $latex \forall \textup{node} \in \textup{Max-heap}, \ [\textup{node.key} \geq \textup{node.childNode.key}]$.

A min-heap is a balanced binary tree such that the key of each node no greater than the key of its child nodes, which is denoted by $latex \forall \textup{node} \in \textup{Min-heap}, \ [\textup{node.key} \leq \textup{node.childNode.key}]$.

Operations

The common operations involving heaps are:

• MaxHeap or MinHeap: create a new, empty, binary heap.
• insert:?adds a new item to the heap.
• findMax or findMin: findMax is for a max-heap and findMin is for a min-heap.
• deleteMax or deleteMin:?returns the node with the maximum/minimum key, removing the node from the heap.
• isEmpty:?returns true if the heap is empty, false otherwise.
• size: returns the number of nodes in the heap.
• buildHeap: builds a new heap from an array of keys.

Applications

• Heapsort:?One of the best sorting methods being in-place and with no quadratic worst-case scenarios, $latex O(n\textup{log}n)$. Input all values into a heap, and then
• Priority queue: The heap is one maximally efficient implementation of an abstract data type called a priority queue.
  • “You can probably think of a couple of easy ways to implement a priority queue using sorting functions and lists. However, inserting into a list is $latex O(n)$?and sorting a list is $latex O(n\textup{log}n)$. We can do better. The classic way to implement a priority queue is using a data structure called a binary heap. A binary heap will allow us both enqueue and dequeue items in $latex O(\textup{log}n)$.”[3]

Insertion Algorithm

To maintain the heap property, a special algorithm is required if a new node is inserted.

Deleting Root[Maximum/Minimum]?Algorithm

To maintain the heap property, a special algorithm is required if a node is deleted.

Search Algorithm

The search algorithm of a heap is a kind of breadth-first search.

(General) Deletion Algorithm

[general deletion algorithm] = [search algorithm] + [deleting root algorithm]

This algorithm is an algorithm that deletes a particular node and maintains the heap?property. The deletion algorithm uses the deleting root?algorithm by viewing a particular node x?to delete as a?root node. Suppose the sub-tree T of which root node is x. By applying the deleting root algorithm toward the sub-tree T, we have a modified heap where x is deleted and the heap maintains the special heap property.

 

References

1. Heap Data Structures | Tutorialspoint
2. Heap (data structure) | Wikipedia
3. 6.8. Priority Queues with Binary Heaps?|?Problem Solving with Algorithms and Data Structures
4. 6.9. Binary Heap Operations?| Problem Solving with Algorithms and Data Structures
5. 6.10. Binary Heap Implementation | Problem Solving with Algorithms and Data Structures