import heapq
from random import random
import matplotlib.pyplot as plt
from time import time
import gc  # garbage collection

size = []
time_heap = []
time_list = []

for i in range(26):
    n = 2 ** i
    size.append(n)

    L = [random() for _ in range(n)]

    print("list", n)
    R = max(1, 2 ** 23 // n)
    gc.collect()
    start = time()
    for _ in range(R):
        L.append(random())
        x = min(L)
        L.remove(x)
    end = time()
    time_list.append((end - start) / R)

    L = None  # avoid MeroryError
    print("heap", n)
    L = [random() for _ in range(n)]
    heapq.heapify(L)  # make L a legal heap
    gc.collect()
    start = time()
    for _ in range(100000):
        heapq.heappush(L, random())
        x = heapq.heappop(L)
    end = time()
    time_heap.append((end - start) / 100000)

plt.title("Average time for insert + delete min")
plt.xlabel("list size")
plt.ylabel("time (seconds)")
plt.plot(size, time_list, 'b.-', label='list (append, min, remove)')
plt.plot(size, time_heap, 'r.-', label='heapq (heappush, heappop)')
plt.xscale('log')
plt.yscale('log')
plt.legend()
plt.show()
