2

Let's say there is a list arr with n elements. Then, heapq.heapify(arr) takes O(n). But I learned heapq.heappush(arr, element) will take O(log n). Isn't heapify same as calling heappush n times?

Maximus S
  • 10,759
  • 19
  • 75
  • 154
  • 1
    See [this](https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity) – Dani Mesejo Sep 29 '19 at 00:02
  • 1
    Also check the [source code for CPython's `heapify` and `_siftup`](https://github.com/python/cpython/blob/master/Lib/heapq.py#L168) – ggorlen Sep 29 '19 at 00:06
  • Calling `heappush()` `n` times would be one way to implement `heapify`, but a cleverer implementation is used - see links already given. – Tim Peters Sep 29 '19 at 00:08

0 Answers0