What is the other common alternative name for a Heap data structure?
Priority Queue
What is the time complexity for retrieving a value from a Heap? (“pop” operation)
What is the time complexity for pushing a value onto the Heap? (“push” operation)
Getting the priority value (minimum or maximum depending on design of the Heap) is O(1) constant time.
Pushing a value onto the Heap takes O(log n) time. In order to maintain the required order and structure properties of a Heap, we push the value to the last available index in the Heap’s array, and then percolate it up through all parents until it is in the appropriate position. This will not exceed the height of the Heap’s tree structure, so O(log n).
What is the time complexity for creating/adding a heap when given a set of values? (“heapify” or “build heap” algorithm)
Heapifying a set of values into a heap takes O(n) time (because for each level of the binary tree we are running into smaller and smaller fractions of n to process, so the summation of all these fractions is equivalent to n.
Last changeda month ago