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

# # Heaps

# Wir beginnen mit der Implementation den wichtigsten Heap Funktionen, naemlich swim und sink. 
# Damit wir diese Testen koennen, implementieren wir zusaetzlich eine Hilfsfunktion plotHeap, die 
# uns den Inhalt des Heaps etwas schoener formatiert ausgibt.

# In[1]:


def swim(a, k):
    while k > 1 and a[int(k//2)] < a[k]:
        a[k//2], a[k] = a[k], a[int(k//2)]
        k = int(k//2)      


# In[2]:


# sinks element k in heap a. N indicates the end of the
# heap. This makes it possible to sink an element in a
# subheap.
def sink(a, k, N = None):
    if N == None: N = len(a) 
    while 2 * k < N:
        j = 2 * k
        if j < N - 1 and a[j] < a[j+1]:
            j += 1
        if not a[k] < a[j]:
            break
        a[j], a[k] = a[k], a[j]
        k = j
        


# In[3]:


import math
def plotHeap(heap):
    if len(heap) <= 1:
        return    

    currentLevel = 0
    for i in range(1, len(heap) ):
        print((heap[i], i), end = " ")
        if i == 2**(currentLevel + 1) -1:
            print("")
            currentLevel += 1
        
        


# Nun koennen wir unsere Funktionen testen.

# In[4]:


testheap = [None, "T", "S", "R", "P", "N", "O", "A", "E", "I", "H", "G"]


# In[5]:


plotHeap(testheap)


# Als erstes fuegen wir ein neues Element, welches die Heap condition verletzt hinzu.

# In[6]:


testheap.append("Z")


# In[7]:


swim(testheap, len(testheap)-1)


# In[8]:


plotHeap(testheap)


# Als naechstes tauschen wir die Wurzel, mit dem letzten Element aus und entfernen dieses. Jetzt ist ein Element an der Wurzel, das da nicht hingehoert. Die Funktion sink bringt dies wieder in Ordnung.

# In[9]:


testheap[1], testheap[-1] = testheap[-1], testheap[1]
testheap.pop()


# In[10]:


plotHeap(testheap)


# In[11]:


sink(testheap, 1)
plotHeap(testheap)


# Dank den Methoden swim und sink koennen wir nun ohne Probleme eine PQ implementieren

# # Priority Queue mittels heap implementieren

# Das Implementieren einer Priority Queue ist nun trivial. Die Funktionen sink und swim uebernehmen die ganze Arbeit

# In[13]:


class PQ:
    def __init__(self):
        self._data = [None]
        
    def isEmpty(self):
        return len(self._data) <= 1
    
    def size(self):
        return len(self._data) -1
    
    def delmax(self):
        self._data[1], self._data[-1] = self._data[-1], self._data[1]
        item = self._data.pop()
        sink(self._data, 1)
        return item
    
    def max(self):
        return self._data[1]
    
    def insert(self, item):
        self._data.append(item)
        swim(self._data, len(self._data) - 1)
        


# Auch sortieren ist jetzt einfach. Wir fügen die Elemente einfach in eine PQ ein und nehmen immer das grösste raus. Da swim und sink beide in $O(log(n))$ sind, ist offensichtlich, dass dies in Zeit $O(n log(n))$ geht (n * Aufwand swim + n * Aufwand sink) 

# In[14]:


testdata = [1,5, 2, 8 , 11]
pq = PQ()
for t in testdata:
    pq.insert(t)

sortedArray = []
while not pq.isEmpty():
    sortedArray.append(pq.delmax())


# In[14]:


sortedArray


# # Heapsort

# Sortieren geht aber noch etwas eleganter, und vor allem ohne zusaechtzlichen Speicherverbrauch, mit dem Heapsort Algorithmus. 

# In[17]:


def heapsort(a):
    N = len(a) -1
    for k in range(int(N//2), 0, -1):
        sink(a, k)
    while N > 1:
        a[1], a[N] = a[N], a[1]
        N -= 1
        sink(a, 1, N)      
        


# In[16]:


testarray = [None, "S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"]
heapsort(testarray)
print(testarray)


# In[ ]: