I'm trying to figure out the time complexity for this whole algorithm. Isit O(nlogn) or O(n)? I've been searching online and some says max heap it's O(nlogn) and some are O(n). I am trying to get the time complexity O(n).
def max_heapify(A, i): left = 2 * i + 1 right = 2 * i + 2 largest = i if left < len(A) and A[left] > A[largest]: largest = left if right < len(A) and A[right] > A[largest]: largest = right if largest != i: A[i], A[largest] = A[largest], A[i] max_heapify(A, largest) def build_max_heap(A): for i in range(len(A) // 2, -1, -1): max_heapify(A, i) return A
I learned from this site it is very helpful. You can see it here. there is a prove how it's complexity is O(n) and O(logn).
A heap is a data structure which supports operations including insertion and retrieval. Each operation has its own runtime complexity.
Maybe you were thinking of the runtime complexity of heapsort which is a sorting algorithm that uses a heap. In that case, the runtime complexity is O(n*log(n)).
The code you have in the question rearranges array elements such that they satisfy the heap property i.e. the value of the parent node is greater than that of the children nodes. The time complexity of the heapify operation is O(n).
Here's an extract from [Wikipedia page on Min-max heap](https://en.wikipedia.org/wiki/Min-max_heap#Build
Creating a min-max heap is accomplished by an adaption of Floyd's linear-time heap construction algorithm, which proceeds in a bottom-up fashion. A typical Floyd's build-heap algorithm goes as follows:
function FLOYD-BUILD-HEAP (h): for each index i from floor(length(h)/2) down to 1 do: push-down(h, i) return h
Here the function
FLOYD-BUILD-HEAP is same as your
build_max_heap function and
push-down is same as your
A suggestion: the naming of your functions is a little confusing. Your
max_heapify is not actually heapifying. It is just a part of the heapify operation. A better name could be something like
push_down (as used in Wikipedia) or