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


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

Check out this link

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

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

comments powered by Disqus