Topics covered in this article:<\/h4>\n\n- What is heap Data Structure?<\/li>\n
- Types heap Data Structure?<\/li>\n
- How to implement heap Data Structure in Python [Code]<\/li>\n
- Insert, remove, retrieve from Heap Datastructure<\/li>\n
- How to print heapified array [Heap] in Tree structure? <\/li>\n
- Usage of Heap Data strcuture<\/li>\n<\/ol>\n<\/div>\n
What is a heap?<\/h2>\n
A heap is a data structure that is used to store a collection of elements, and the elements are arranged in a way that satisfies the heap property. The heap property is the property that states that for every node in the heap, the key of the parent node is less than or equal to the key of the child node. The keys can be any type that is comparable, such as integers or strings.<\/p>\n
Types of heaps:<\/h2>\n
There are two types of heaps: max heap and min heap. In a max heap, the value of each node is greater than or equal to the values of its children whereas, in a min heap, the value of each node is less than or equal to the values of its children. Therefore, the first node in the “max heap” always returns the highest value while in the min heap, it returns the lowest value.
\n
![\"Types](\"https:\/\/vmlogger.com\/algorithms\/wp-content\/uploads\/sites\/15\/2023\/03\/Types-of-heap-1024x620.png\")
Types of Heap Data Structure<\/p><\/div><\/p>\n
Implementation:<\/h3>\n
A heap can be implemented using an array or a tree data structure [as shown in the above picture]. The array implementation is simpler and more efficient in terms of memory usage. The tree implementation, on the other hand, is more flexible and allows for more efficient insertion and deletion operations.<\/p>\n
Here, in this article, we are going to use the array<\/code> data structure of python to represent the heap<\/code> data structure. Following are some rules, how
\nIn the array implementation, the heap is represented as an array where the first element is the root of the tree, the second and third elements are the children of the root, and so on. For a given node at index i,<\/code> its left child is located at index 2i+1 <\/code>, and its right child is located at index 2i+2<\/code>. The parent of a node at index I<\/code> is located at the index floor((i-1)\/2)<\/code>.<\/p>\n\nInfo:<\/h3>\n
In the tree implementation, the heap is represented as a binary tree where the nodes are arranged in a way that satisfies the heap property. The tree implementation allows for more efficient insertion and deletion operations, but it requires more memory to store the pointers to the child nodes.\n<\/p><\/div>\n
Operations performed on a Heap:<\/h2>\n
The main operations that can be performed on a heap are insertion <\/code> or deletion<\/code>. One more operation which is retrieval<\/code> can be performed. As explained above, this operation returns the very first value stored in a heap. In min heap<\/code>, the value stored as a first node, will be the lowest among all but in max heap<\/code> it will be the highest value.<\/p>\nInsertion:<\/h4>\n
To insert an element into a heap, we add the element to the end of the array or the bottom of the tree, and then we compare the key of the element with the key of its parent. If the key of the element is greater than the key of its parent in a max heap, or less than the key of its parent in a min heap, we swap the element with its parent, and we repeat the process until the heap property is satisfied.<\/p>\n
Deletion:<\/h4>\n
To delete the minimum or maximum element from a heap, we remove the root of the tree, which is the minimum or maximum element depending on whether the heap is a min heap or a max heap. We then replace the root with the last element in the array or the bottom of the tree, and we compare the key of the new root with the keys of its children. If the key of the new root is less than the keys of its children in a max heap, or greater than the keys of its children in a min heap, we swap the new root with the larger or smaller child, and we repeat the process until the heap property is satisfied.<\/p>\n
Retrieval:<\/h4>\n
To retrieve the minimum or maximum element from a heap, we simply return the root of the tree, which is the minimum or maximum element depending on whether the heap is a min heap or a max heap.<\/p>\n
Python Code to implement minHeap<\/code> Class<\/h2>\n\r\nclass MinimumHeap:\r\n def __init__(self, array):\r\n self.heap = self.__buildHeap(array)\r\n\r\n # private methods used within this class\r\n def __buildHeap(self, array):\r\n parentNodeIdx = (len(array) - 2) \/\/ 2\r\n for idx in reversed(range(parentNodeIdx + 1)):\r\n self.__moveDown(array, idx, len(array) - 1)\r\n return array\r\n \r\n def __moveUp(self, heap, startIdx):\r\n parentIdx = (startIdx - 1) \/\/ 2\r\n while startIdx > 0 and heap[startIdx] < heap[parentIdx]:\r\n heap[startIdx], heap[parentIdx] = heap[parentIdx], heap[startIdx]\r\n startIdx = parentIdx\r\n parentIdx = (startIdx - 1) \/\/ 2\r\n \r\n def __moveDown(self, heap, startIdx, endIdx):\r\n childOneIdx = startIdx * 2 + 1\r\n while childOneIdx <= endIdx:\r\n if (startIdx * 2 + 2) <= endIdx:\r\n childTwoIdx = startIdx * 2 + 2\r\n else:\r\n childTwoIdx = -1\r\n if childTwoIdx != -1 and heap[childTwoIdx] < heap[childOneIdx]:\r\n possibleSwapIdx = childTwoIdx\r\n else:\r\n possibleSwapIdx = childOneIdx\r\n if heap[possibleSwapIdx] < heap[startIdx]:\r\n heap[startIdx], heap[possibleSwapIdx] = heap[possibleSwapIdx], heap[startIdx]\r\n startIdx = possibleSwapIdx\r\n childOneIdx = startIdx * 2 + 1\r\n else:\r\n return\r\n\r\n # public methods used to add, get and \r\n # insert a new item in the heap\r\n\r\n def insert(self, item):\r\n self.heap.append(item)\r\n self.__moveUp(self.heap, len(self.heap) - 1)\r\n\r\n def remove(self):\r\n lastIdx = len(self.heap) - 1\r\n self.heap[0], self.heap[lastIdx] = self.heap[lastIdx], self.heap[0]\r\n self.heap.pop()\r\n self.__moveDown(self.heap, 0, len(self.heap) - 1)\r\n \r\n # returns heapified array\r\n def getHeapArray(self):\r\n return self.heap\r\n\r\n # returns minimum value\r\n def getMinValue(self):\r\n return self.heap[0]\r\n\r\n<\/pre>\nPython Code to implement maxHeap<\/code> Class<\/h2>\nFor creating a maxHeap<\/code> data structure there is a very minor change, you need to make in the above code. While inserting a new element, instead of moving the smaller element up, you should be moving the bigger element up. Similarly, while moving down, instead of moving bigger elements down, you need to move smaller elements down. These are the only two changes and the rest are going to be exactly the same.<\/p>\n\r\nclass MaximumHeap:\r\n def __init__(self, array):\r\n self.heap = self.__buildHeap(array)\r\n\r\n # private methods used within this class\r\n def __buildHeap(self, array):\r\n parentNodeIdx = (len(array) - 2) \/\/ 2\r\n for idx in reversed(range(parentNodeIdx + 1)):\r\n self.__moveDown(array, idx, len(array) - 1)\r\n return array\r\n \r\n def __moveUp(self, heap, startIdx):\r\n parentIdx = (startIdx - 1) \/\/ 2\r\n while startIdx > 0 and heap[startIdx] > heap[parentIdx]:\r\n heap[startIdx], heap[parentIdx] = heap[parentIdx], heap[startIdx]\r\n startIdx = parentIdx\r\n parentIdx = (startIdx - 1) \/\/ 2\r\n \r\n def __moveDown(self, heap, startIdx, endIdx):\r\n childOneIdx = startIdx * 2 + 1\r\n while childOneIdx <= endIdx:\r\n if (startIdx * 2 + 2) <= endIdx:\r\n childTwoIdx = startIdx * 2 + 2\r\n else:\r\n childTwoIdx = -1\r\n if childTwoIdx != -1 and heap[childTwoIdx] > heap[childOneIdx]:\r\n possibleSwapIdx = childTwoIdx\r\n else:\r\n possibleSwapIdx = childOneIdx\r\n if heap[possibleSwapIdx] > heap[startIdx]:\r\n heap[startIdx], heap[possibleSwapIdx] = heap[possibleSwapIdx], heap[startIdx]\r\n startIdx = possibleSwapIdx\r\n childOneIdx = startIdx * 2 + 1\r\n else:\r\n return\r\n\r\n # public methods used to add, get and \r\n # insert a new item in the heap\r\n\r\n def insert(self, item):\r\n self.heap.append(item)\r\n self.__moveUp(self.heap, len(self.heap) - 1)\r\n\r\n def remove(self):\r\n lastIdx = len(self.heap) - 1\r\n self.heap[0], self.heap[lastIdx] = self.heap[lastIdx], self.heap[0]\r\n self.heap.pop()\r\n self.__moveDown(self.heap, 0, len(self.heap) - 1)\r\n \r\n # returns heapified array\r\n def getHeapArray(self):\r\n return self.heap\r\n\r\n # returns minimum value\r\n def getMinValue(self):\r\n return self.heap[0]\r\n<\/pre>\nPrint Heapified array in Tree structure<\/h2>\n
In the above implementation, the class will return heapified array which will not be easy to visualize in a tree-like structure. Therefore, I have created a simple but not so good<\/code> function which prints your heapified array<\/code> in a tree structure in your console.<\/p>\n\r\n # print heapified array in tree structure\r\n def getHeapTree(self):\r\n k = level = 0\r\n tree = \"\"\r\n size = len(self.heap) - 1\r\n lSize = int(math.floor(math.log(size, 2))) + 1\r\n totalSpace = (2**lSize)*2\r\n while k <= size:\r\n levelMax = 2**level\r\n for l in range(1, levelMax+1):\r\n tree = tree + \" \"*int(totalSpace\/(2**level + 1)) + str(self.heap[k])\r\n k = k + 1\r\n if k > size:\r\n break\r\n level += 1\r\n tree = tree + \"\\n\\n\"\r\n return tree\r\n<\/pre>\nHere is the result of the above function for minHeap<\/code> and maxHeap<\/code> structured data.
\n
What is a heap?<\/h2>\n
A heap is a data structure that is used to store a collection of elements, and the elements are arranged in a way that satisfies the heap property. The heap property is the property that states that for every node in the heap, the key of the parent node is less than or equal to the key of the child node. The keys can be any type that is comparable, such as integers or strings.<\/p>\n
Types of heaps:<\/h2>\n
There are two types of heaps: max heap and min heap. In a max heap, the value of each node is greater than or equal to the values of its children whereas, in a min heap, the value of each node is less than or equal to the values of its children. Therefore, the first node in the “max heap” always returns the highest value while in the min heap, it returns the lowest value.
\n
Types of Heap Data Structure<\/p><\/div><\/p>\n
Implementation:<\/h3>\n
A heap can be implemented using an array or a tree data structure [as shown in the above picture]. The array implementation is simpler and more efficient in terms of memory usage. The tree implementation, on the other hand, is more flexible and allows for more efficient insertion and deletion operations.<\/p>\n
Here, in this article, we are going to use the In the tree implementation, the heap is represented as a binary tree where the nodes are arranged in a way that satisfies the heap property. The tree implementation allows for more efficient insertion and deletion operations, but it requires more memory to store the pointers to the child nodes.\n<\/p><\/div>\n The main operations that can be performed on a heap are To insert an element into a heap, we add the element to the end of the array or the bottom of the tree, and then we compare the key of the element with the key of its parent. If the key of the element is greater than the key of its parent in a max heap, or less than the key of its parent in a min heap, we swap the element with its parent, and we repeat the process until the heap property is satisfied.<\/p>\n To delete the minimum or maximum element from a heap, we remove the root of the tree, which is the minimum or maximum element depending on whether the heap is a min heap or a max heap. We then replace the root with the last element in the array or the bottom of the tree, and we compare the key of the new root with the keys of its children. If the key of the new root is less than the keys of its children in a max heap, or greater than the keys of its children in a min heap, we swap the new root with the larger or smaller child, and we repeat the process until the heap property is satisfied.<\/p>\n To retrieve the minimum or maximum element from a heap, we simply return the root of the tree, which is the minimum or maximum element depending on whether the heap is a min heap or a max heap.<\/p>\n For creating a In the above implementation, the class will return heapified array which will not be easy to visualize in a tree-like structure. Therefore, I have created a simple but Here is the result of the above function for array<\/code> data structure of python to represent the heap<\/code> data structure. Following are some rules, how
\nIn the array implementation, the heap is represented as an array where the first element is the root of the tree, the second and third elements are the children of the root, and so on. For a given node at index i,<\/code> its left child is located at index 2i+1 <\/code>, and its right child is located at index 2i+2<\/code>. The parent of a node at index I<\/code> is located at the index floor((i-1)\/2)<\/code>.<\/p>\nInfo:<\/h3>\n
Operations performed on a Heap:<\/h2>\n
insertion <\/code> or deletion<\/code>. One more operation which is retrieval<\/code> can be performed. As explained above, this operation returns the very first value stored in a heap. In min heap<\/code>, the value stored as a first node, will be the lowest among all but in max heap<\/code> it will be the highest value.<\/p>\nInsertion:<\/h4>\n
Deletion:<\/h4>\n
Retrieval:<\/h4>\n
Python Code to implement
minHeap<\/code> Class<\/h2>\n\r\nclass MinimumHeap:\r\n def __init__(self, array):\r\n self.heap = self.__buildHeap(array)\r\n\r\n # private methods used within this class\r\n def __buildHeap(self, array):\r\n parentNodeIdx = (len(array) - 2) \/\/ 2\r\n for idx in reversed(range(parentNodeIdx + 1)):\r\n self.__moveDown(array, idx, len(array) - 1)\r\n return array\r\n \r\n def __moveUp(self, heap, startIdx):\r\n parentIdx = (startIdx - 1) \/\/ 2\r\n while startIdx > 0 and heap[startIdx] < heap[parentIdx]:\r\n heap[startIdx], heap[parentIdx] = heap[parentIdx], heap[startIdx]\r\n startIdx = parentIdx\r\n parentIdx = (startIdx - 1) \/\/ 2\r\n \r\n def __moveDown(self, heap, startIdx, endIdx):\r\n childOneIdx = startIdx * 2 + 1\r\n while childOneIdx <= endIdx:\r\n if (startIdx * 2 + 2) <= endIdx:\r\n childTwoIdx = startIdx * 2 + 2\r\n else:\r\n childTwoIdx = -1\r\n if childTwoIdx != -1 and heap[childTwoIdx] < heap[childOneIdx]:\r\n possibleSwapIdx = childTwoIdx\r\n else:\r\n possibleSwapIdx = childOneIdx\r\n if heap[possibleSwapIdx] < heap[startIdx]:\r\n heap[startIdx], heap[possibleSwapIdx] = heap[possibleSwapIdx], heap[startIdx]\r\n startIdx = possibleSwapIdx\r\n childOneIdx = startIdx * 2 + 1\r\n else:\r\n return\r\n\r\n # public methods used to add, get and \r\n # insert a new item in the heap\r\n\r\n def insert(self, item):\r\n self.heap.append(item)\r\n self.__moveUp(self.heap, len(self.heap) - 1)\r\n\r\n def remove(self):\r\n lastIdx = len(self.heap) - 1\r\n self.heap[0], self.heap[lastIdx] = self.heap[lastIdx], self.heap[0]\r\n self.heap.pop()\r\n self.__moveDown(self.heap, 0, len(self.heap) - 1)\r\n \r\n # returns heapified array\r\n def getHeapArray(self):\r\n return self.heap\r\n\r\n # returns minimum value\r\n def getMinValue(self):\r\n return self.heap[0]\r\n\r\n<\/pre>\n
Python Code to implement
maxHeap<\/code> Class<\/h2>\nmaxHeap<\/code> data structure there is a very minor change, you need to make in the above code. While inserting a new element, instead of moving the smaller element up, you should be moving the bigger element up. Similarly, while moving down, instead of moving bigger elements down, you need to move smaller elements down. These are the only two changes and the rest are going to be exactly the same.<\/p>\n\r\nclass MaximumHeap:\r\n def __init__(self, array):\r\n self.heap = self.__buildHeap(array)\r\n\r\n # private methods used within this class\r\n def __buildHeap(self, array):\r\n parentNodeIdx = (len(array) - 2) \/\/ 2\r\n for idx in reversed(range(parentNodeIdx + 1)):\r\n self.__moveDown(array, idx, len(array) - 1)\r\n return array\r\n \r\n def __moveUp(self, heap, startIdx):\r\n parentIdx = (startIdx - 1) \/\/ 2\r\n while startIdx > 0 and heap[startIdx] > heap[parentIdx]:\r\n heap[startIdx], heap[parentIdx] = heap[parentIdx], heap[startIdx]\r\n startIdx = parentIdx\r\n parentIdx = (startIdx - 1) \/\/ 2\r\n \r\n def __moveDown(self, heap, startIdx, endIdx):\r\n childOneIdx = startIdx * 2 + 1\r\n while childOneIdx <= endIdx:\r\n if (startIdx * 2 + 2) <= endIdx:\r\n childTwoIdx = startIdx * 2 + 2\r\n else:\r\n childTwoIdx = -1\r\n if childTwoIdx != -1 and heap[childTwoIdx] > heap[childOneIdx]:\r\n possibleSwapIdx = childTwoIdx\r\n else:\r\n possibleSwapIdx = childOneIdx\r\n if heap[possibleSwapIdx] > heap[startIdx]:\r\n heap[startIdx], heap[possibleSwapIdx] = heap[possibleSwapIdx], heap[startIdx]\r\n startIdx = possibleSwapIdx\r\n childOneIdx = startIdx * 2 + 1\r\n else:\r\n return\r\n\r\n # public methods used to add, get and \r\n # insert a new item in the heap\r\n\r\n def insert(self, item):\r\n self.heap.append(item)\r\n self.__moveUp(self.heap, len(self.heap) - 1)\r\n\r\n def remove(self):\r\n lastIdx = len(self.heap) - 1\r\n self.heap[0], self.heap[lastIdx] = self.heap[lastIdx], self.heap[0]\r\n self.heap.pop()\r\n self.__moveDown(self.heap, 0, len(self.heap) - 1)\r\n \r\n # returns heapified array\r\n def getHeapArray(self):\r\n return self.heap\r\n\r\n # returns minimum value\r\n def getMinValue(self):\r\n return self.heap[0]\r\n<\/pre>\n
Print Heapified array in Tree structure<\/h2>\n
not so good<\/code> function which prints your heapified array<\/code> in a tree structure in your console.<\/p>\n\r\n # print heapified array in tree structure\r\n def getHeapTree(self):\r\n k = level = 0\r\n tree = \"\"\r\n size = len(self.heap) - 1\r\n lSize = int(math.floor(math.log(size, 2))) + 1\r\n totalSpace = (2**lSize)*2\r\n while k <= size:\r\n levelMax = 2**level\r\n for l in range(1, levelMax+1):\r\n tree = tree + \" \"*int(totalSpace\/(2**level + 1)) + str(self.heap[k])\r\n k = k + 1\r\n if k > size:\r\n break\r\n level += 1\r\n tree = tree + \"\\n\\n\"\r\n return tree\r\n<\/pre>\n
minHeap<\/code> and maxHeap<\/code> structured data.
\n
![\"Print](\"https:\/\/vmlogger.com\/algorithms\/wp-content\/uploads\/sites\/15\/2023\/03\/Screenshot-2023-03-28-at-17.49.15.png\")