What's the time complexity for max heap?

Hal Source

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
``````
pythontime-complexityheap

answered 6 months ago Syed Sohan #1

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).

answered 6 months ago George Kettleborough #2

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)).

answered 6 months ago Lakshay Garg #3

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).

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.[10] A typical Floyd's build-heap algorithm[11] 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 `max_heapify` function.

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 `fix_heap`.