#!/usr/bin/env python
# coding: utf-8

# # Priority Queues

# ## Zwei einfache Implementationen mittels Arrays

# Die erste Implementation verwendet ein einfaches, unsortiertes Array. Wenn max oder delmax aufgerufen werden, 
# wird das groesste Element gesucht und mit dem letzten vertauscht.

# In[8]:


class MaxPQUnorderedArray:
    
    def __init__(self):
        self._data = []
    
    def insert(self, k):
        self._data.append(k)
    
    def max(self):
        self._largestToEnd()
        return self._data[-1]
            
    def delMax(self):
        self._largestToEnd()
        return self._data.pop()
    
    def _largestToEnd(self):
        if len(self._data) == 0:
            return
        
        maxElem = self._data[0]            
        maxIndex = 0
        for i, d in enumerate(self._data):
            if (maxElem < d):
                maxElem = self._data[i]
                maxIndex = i
        self._data[maxIndex], self._data[-1] = self._data[-1], self._data[maxIndex]
        
    
        
    def isEmpty(self):
        return len(self._data) == 0
    
    def size(self):
        return len(self._data)


# Bei der zweiten einfachen Implementation, wird das neue Element jeweils an die richtige Position im Array eingefuegt. Die Insert methode wird dadurch aufwaendiger, dafuer sind die Methoden max und delmax sehr einfach und effizient.

# In[7]:


class MaxPQOrderedArray:
    
    def __init__(self):
        self._data = []
    
    def insert(self, k):
        
        # Suche im sortierten Array data die Position vom neuen Element
        idx = 0
        while (idx < len(self._data) and self._data[idx] < k):            
            idx += 1
        self._data.insert(idx, k)        
        
    def max(self):
        if self.isEmpty():
            return None
        else:
            return self._data[-1]
            
    def delMax(self):
        return self._data.pop()
        
        
    def isEmpty(self):
        return len(self._data) == 0
    
    def size(self):
        return len(self._data)


# #### Komplexität

# In[3]:


import timeit
import random


# In[10]:


def insertNElements(pq, N):
    for i in range(0, N):
        pq.insert(i)


# In[6]:


def removeLargestNElements(pq, N):
    for i in range(0, N):
        pq.delMax()


# In[11]:


orderedPQ = MaxPQOrderedArray()
unorderedPQ = MaxPQUnorderedArray()

print("insert ordered ", timeit.timeit(lambda: insertNElements(orderedPQ, 10000), number = 1))
print("insert unordered", timeit.timeit(lambda: insertNElements(unorderedPQ, 10000), number = 1))
print("removeLargest ordered", timeit.timeit(lambda: removeLargestNElements(orderedPQ, 10000), number = 1))
print("removeLargest unordered", timeit.timeit(lambda: removeLargestNElements(unorderedPQ, 10000), number = 1))


# In[ ]:





# ## Beispiel Client

# Eine typische Beispielanwendung ist, dass man aus einem sehr grossen Datenstrom die groessten Elemente extrahieren moechte. Um das Beispiel hier minimal zu halten, und trotzdem die Moeglichkeit zu haben grosse Streams zu generiern, ziehen wir Zufallszahlen von einer Normalverteilung.

# Die folgende Funktion generiert einen Stream von $n$ normalverteilen Zufallszahlen

# In[12]:


import random

def numberGen(n):
    num = 0
    while num < n:
        yield random.normalvariate(0, 1)
        num += 1


# Unser Beispielclient fuegt $N$ zufaellig Zahlen in eine Priorityqueue ein. Wenn die gewuenschte Anzahl von groessten Zahlen $M$ erreicht ist wird immer die jeweils kleinste entfernt, um wieder Platz fuer eine neue groesste Zahl zu schaffen. Am ende sind dann die $M$ groessten Zahlen in der Queue, und wir muessen diese nur noch entfernen.
# 
# *Achtung: Dies wuerde man am besten mit einer Minimumsorientierten Priorityqueue loesen. In der Praxis hat man aber selten beide Varianten zur Verfuegung. Wir helfen uns damit, dass wir einfach das negative der Zufallszahl hinzufuegen, und dies beim auslesen nochmals negieren.*

# In[13]:


def printSmallestNumber(pq, M, N):
    
    for number in numberGen(N):
        pq.insert(-1.0 * number)
        if (pq.size() > M):   
            pq.delMax();           
    
    while not pq.isEmpty():
        print(-1.0 * pq.delMax())


# In[19]:


printSmallestNumber(MaxPQUnorderedArray(), 10, 10000000)


# *Uebung: Schreiben Sie einen Client, der aus einem gegebenen Text mittels demselben Verfahren die laengsten $M$ Woerter bestimmt.*

# In[ ]: