> On Dec 12, 2016, at 8:12 AM, Raymond Hettinger <raymond.hettin...@gmail.com>
> wrote:
>
> The heapify() algorithm is well known and well studied. A quick Google
> search turns up plenty of explanations:
> https://www.google.com/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=complexity%20of%20heapify
>
>
> algorithm - How can building a heap be O(n) time complexity? - StackOverflow
> https://www.google.com/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=complexity%20of%20heapify
>
> Data Structures Heap, Heap Sort & Priority Queue
> https://www.google.com/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=complexity%20of%20heapify
> Sub tree rooted at i is a max heap. Simple bound:
> – O(n) calls to MAX-HEAPIFY,
> – Each of which takes O(lg n), – Complexity: O(n lg n).
> – Thus, the running time of BUILD-MAX-HEAP is O(n).
>
> Here's a more detailed explanation:
> http://www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf
>
> If you have other follow-ups, please take this discussion to another list.
> This list is for the development of the Python core and not for general
> questions about algorithms or use of the language.
I forgot to attach the measurements that demonstrate the O(n) complexity:
# Python 3 Code
from heapq import heapify
from random import randrange
cmp_cnt = 0
class Int(int):
def __lt__(self, other):
global cmp_cnt
cmp_cnt += 1
return super.__lt__(self, other)
def trial(n):
global cmp_cnt
data = [Int(randrange(1000000)) for i in range(n)]
cmp_cnt = 0
heapify(data)
return cmp_cnt
for n in [100, 1000, 10000, 100000, 1000000, 10000000]:
print("n = {:<10d} compares = {}".format(n, trial(n)))
Which outputs:
n = 100 compares = 155
n = 1000 compares = 1620
n = 10000 compares = 16446
n = 100000 compares = 164779
n = 1000000 compares = 1649165
n = 10000000 compares = 16493429
_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
https://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
