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 .

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 .

###### 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, . 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 and sorting a list is . 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 .”[3]

- “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 and sorting a list is . We can do better. The classic way to implement a priority queue is using a data structure called a

###### 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

- Heap Data Structures | Tutorialspoint
- Heap (data structure) | Wikipedia
- 6.8. Priority Queues with Binary Heaps | Problem Solving with Algorithms and Data Structures
- 6.9. Binary Heap Operations | Problem Solving with Algorithms and Data Structures
- 6.10. Binary Heap Implementation | Problem Solving with Algorithms and Data Structures