• A A

## Difference Between Stack and Heap

Stack vs Heap

Stack is an ordered list in which insertion and deletion of list items can be done only in one end called the top. Due to this reason, stack is considered as a Last in First out (LIFO) data structure. Heap is a special data structure that is based on trees and it satisfies a special property called the heap property. Also, a heap is a complete tree, which means that there are no gaps between the leaves of the tree i.e. in a complete tree every level is filled in before adding a new level to the tree and the nodes in a given level are filled from left to right.

What is Stack?

As mentioned earlier, stack is a data structure in which elements are added and removed from only one end called the top. Stacks allow only two fundamental operations called push and pop. The push operation adds a new element to the top of the stack. The pop operation removes an element from the top of the stack. If the stack is already full, when a push operation is performed, it is considered as a stack overflow. If a pop operation is performed on an already empty stack, it is considered as a stack underflow. Due to the small number of operations that could be performed on a stack, it is considered as a restricted data structure. Additionally, according to the way that the push and pop operations are defined, it is clear that elements that were added last in to the stack go out of the stack first. Therefore stack is considered as a LIFO data structure.

What is Heap?

As mentioned earlier, heap is a complete tree that satisfies the heap property. Heap property states that, if y is a child node of x then the value stored in node x should be greater than or equal to the value stored in node y (i.e. value(x) ≥ value(y)). This property implies that the node with the greatest value would always be placed at the root. A heap constructed using this property is called a max-heap. There is another variation of the heap property that states the reverse of this. (i.e. value(x) ≤ value(y)). This implies that the node with the smallest value would always be placed at the root, thus called a min-heap. There is a wide range of operations performed on heaps such as finding minimum (in min-heaps) or maximum (in max-heaps), deleting minimum (in min-heaps) or maximum (in max-heaps), increasing (in max-heaps) or decreasing (in min-heaps) key, etc.

What is the difference between Stack and Heap?

The main difference between stacks and heaps is that while stack is a linear data structure, heap is a non linear data structure. Stack is an ordered list that follows the LIFO property, while the heap is a complete tree that follows the heap property. Furthermore, stack is a restricted data structure that supports only a limited number of operations as push and pop, while heap supports a wide range of operations such as finding and deleting the minimum or maximum, increasing or decreasing the key and merging.

Related posts: