CODEWITHSUNDEEP
pythontime-complexityheap
Hal
Hal

Reputation: 372

What's the time complexity for max heap?

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

Upvotes: 0

Views: 3958

Answers (2)

lakshayg
lakshayg

Reputation: 2173

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.

Upvotes: 1

George Kettleborough
George Kettleborough

Reputation: 423

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

Upvotes: 0

Related Questions