Binary Heap ( swim, sink, insert delMax)

Codeblock 1

Kind zu groß, klettert nach oben

def swim(self, k):
    while k > 1 and self.pq[k//2] < self.pq[k]:
        self.pq[k], self.pq[k//2] = self.pq[k//2], self.pq[k]
        k = k // 2

2. solange ich nicht die Wurzel bin und größer als mein Vater bin

3. tausche mich mit meinem Vater

4. und geh auf die Position des Vaters

Codeblock 2

Vater zu klein, sinkt zum größeren Kind

def sink(self, k):
    while 2*k <= self.N:
        j = 2*k
        if j < self.N and self.pq[j] < self.pq[j+1]:
            j += 1
        if not self.pq[k] < self.pq[j]:
            break
        self.pq[k], self.pq[j] = self.pq[j], self.pq[k]
        k = j

2. solange ich überhaupt ein linkes Kind habe

3. zeig erstmal aufs linke Kind

4. gibt's ein rechtes Kind und ist es größer? dann zeig dorthin

5. bin ich schon größer als das gewählte Kind? dann fertig

6. sonst tausche mich mit dem Kind

7. und geh auf die Position des Kindes

Codeblock 3

hinten anhängen, hochklettern lassen

def insert(self, x):
    self.N += 1
    self.pq[self.N] = x
    self.swim(self.N)

2. Heap wird um eins größer

3. das Neue kommt ans Ende

4. und schwimmt von dort hoch

Codeblock 4

auto

def delMax(self):
    max_val = self.pq
    self.pq, self.pq[self.N] = self.pq[self.N], self.pq
    self.N -= 1
    self.sink(1)
    self.pq[self.N+1] = None
    return max_val

1. merk dir die Wurzel, das ist das Maximum

2. tausch die Wurzel mit dem letzten Element

3. Heap wird um eins kleiner

4. die neue Wurzel sinkt an ihren Platz

5. Referenz auf das Entfernte löschen (Loitering)

6. und gib das Gemerkte zurück