Pairing Heaps

[Kirby.exe]

Also ich möchte gerne einen Pairing Heap implementieren. Hierbei habe ich ein gewisses Problem...Ich würde es gerne so implementieren, dass Zugriffe wie insert() und findMin() in O(1) durchlaufen. Hingegen deleteMin() und decreseKey() in O(log n) durchlaufen.

Mir würde jetzt ein Array spontan einfallen um O(1) zu erhalten. Jedoch wäre mein anderer Gedanke einfach einen Node-Container zu erstellen und diese Nodes per Referenz zu linken xD Nur weiß ich hierbei nicht ob das für deleteMin() und decreseKey() auf O(log n) kommt.

Wie würdet Ihr es implementieren?

 

[mihe7]

Wie würdet Ihr es implementieren?

Mit Nodes.

 

[Kirby.exe]

Mit Nodes.

Na dann probiere ich mal mein Glück

 

[Kirby.exe]

Ich zerbreche mir gerade den Kopf über decreaseKey() und sehe nicht so richtig wie ich das implementieren könnte...Hier ist mein bisheriger PairingHeap:

import java.util.ArrayList;

public class PairingHeap {
    
    private HeapNode minNode;
    private int size;

    public PairingHeap() {
        minNode = null;
        size = 0;
    }
    
    public void insert(int item, int priority) {
        HeapNode curr = new HeapNode(item, priority);
        if(isEmpty()){
            this.minNode = curr;
            this.size++;
        }
        else{
            this.minNode =  merge(minNode, curr);
            this.size++;
        }
    }
      
    
    private HeapNode merge(HeapNode node1, HeapNode node2){
        HeapNode subtreeHeadNode;
        
        if(node1.key > node2.key){
            node2.addChild(node1);
            subtreeHeadNode = node2;
        }
        else{
            node1.addChild(node2);
            subtreeHeadNode = node1;
        }

        return subtreeHeadNode;
    }
    
    public void decreaseKey(int item, int newPriority) {
        
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public int findMin() {
        return isEmpty() ? -1 : minNode.item;
    }
    
    public int deleteMin(){
        if(isEmpty()) return -1;
        
        HeapNode tempHolder = this.minNode;

        if(this.size == 1){
            this.size--;
            minNode = null;
            return tempHolder.item;
        }

        ArrayList<HeapNode> childQueue = new ArrayList<>();
        for(HeapNode child: minNode.childs){
            childQueue.add(child);
        }

        while(childQueue.size() > 1){
            HeapNode subtreeRoot = merge(childQueue.get(0), childQueue.get(1));
            childQueue.remove(0);
            childQueue.remove(0);
            childQueue.add(subtreeRoot);
        }

        this.minNode = childQueue.get(0);
        this.size--;
        return tempHolder.item;
    }
}

class HeapNode{
    
    public int item;
    public int key;
    public ArrayList<HeapNode> childs;
    
    public HeapNode() {
        this.item = -1;
        this.key = -1;
        this.childs = null;
    }
    
    public HeapNode(int item, int key) {
        this.item = item;
        this.key = key;
        this.childs = null;
    }
    
    public void addChild(HeapNode node) {
        if(childs == null) childs = new ArrayList<>();
        childs.add(node);
    }
}

 

[mihe7]

Dem Original-Paper https://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf nach braucht Dein HeapNode drei Zeiger (bzw. zwei und ein Flag).

 

[Kirby.exe]

Was meinst du mit Flag?
Also ich habe eine Implementation gesehen, wo jeder Node ein Left Child Pointer, einen Right Sibling Pointer und einen Key Value hat xD

 

[mihe7]

Schau Dir mal S. 114 und 115 an (PDF Seite 4 und 5). Da wird erklärt, dass jeder Knoten drei Zeiger braucht: einen auf den ersten Kindknoten, einen den rechten Geschwisterknoten und einen auf den Elternknoten. Nun kann es Knoten mit nur einem Kindknoten geben und dafür muss man wohl ein Flag haben, um zu wissen, ob es sich um einen linken oder rechten Kindknoten handelt. Man kommt auch mit zwei Zeigern aus, wenn man den Zeiger auf den Geschwisterknoten auf den Elternknoten zeigen lässt, falls es keine weiteren Geschwister gibt.

 

[Kirby.exe]

Also ich habe die Implementation von HeapNode nun wie folgt:

class HeapNode{
  
    public int item;
    public int key;
    public HeapNode leftChild;
    public HeapNode rightSibling;
    public HeapNode parent;
  
    public HeapNode(int item, int key) {
        this.item = item;
        this.key = key;
        this.leftChild = null;
        this.rightSibling = null;
        this.parent = null;
    }
  
    public void addChild(HeapNode node) {
        if(leftChild == null) {
            leftChild = node;
            return;
        }
      
        if(rightSibling == null) {
            rightSibling = node;
        }
      
        HeapNode temp = rightSibling;
        while(temp.rightSibling != null) {
            temp = temp.rightSibling;
        }
      
        if(temp != null) {
            temp.rightSibling = node;
        }
    }
}

Dennoch verstehe ich es noch nicht so ganz...Ich versuche gerade alles nochmal neu zu machen und zwar so wie es im Paper steht. Somit angefangen bei Insert.

Dort steht man konstruiere einen ein-elementigen Heap und merge die beiden und hier ist mein Problem...Wie merge ich denn bitte zwei Heaps? Gehe ich mit zwei Pointern durch und fange an der Wurzel an? Wonach entscheide ich welchen Heap ich wo rein merge?

Hier ist meine PairingHeap Klassen:

public class PairingHeap {
  
    private HeapNode minNode;

    public PairingHeap() {
        minNode = null;
    }
  
    public void insert(int item, int priority) {
        PairingHeap temp = new PairingHeap();
        temp.insert(new HeapNode(item, priority));
        this.merge(temp);
    }
    
    public void insert(HeapNode node) {
        if(minNode == null) {
            minNode = node;
        }
    }
  
    private void merge(PairingHeap tree){
        return;
    }
  
    public void decreaseKey(int item, int newPriority) {
      
    }
  
    public int findMin() {
        return minNode == null ? -1 : minNode.item;
    }
  
    public int deleteMin(){
       return -1;
    }
}

Edit:

Da der (also der bereits existierende) Main Heap ein min Heap ist und der zu mergende Heap nur ein Element enthält sind ja beide min Heaps

 

[mihe7]

Wie merge ich denn bitte zwei Heaps? Gehe ich mit zwei Pointern durch und fange an der Wurzel an? Wonach entscheide ich welchen Heap ich wo rein merge?

Du vergleichst die Wurzelknoten. Der kleinere wird zur Wurzel des neuen Heaps und der größere wird zu deren linken Kind.

 

[Kirby.exe]

Du vergleichst die Wurzelknoten. Der kleinere wird zur Wurzel des neuen Heaps und der größere wird zu deren linken Kind.

und was ist wenn der größere schon ein linkes Kind hat? Wird er dann das rechte Kind?

 

[mihe7]

@mrBrown, vor Dir bleibt man doch nirgends verschont. Wenn ich mal aus dem Paper die erste Referenz anführen darf:

[1] M. R. Brown, "Implementation and analysis of binomial queue algorithms", SIAM J. Comput. 7 (1978), 298-319.

 

[mihe7]

und was ist wenn der größere schon ein linkes Kind hat? Wird er dann das rechte Kind?

Geschwisterchen, ja. Die Wurzelknoten eins Pairing Heaps haben keine Geschwister sondern nur linke Kinder, wenn ich es richtig verstehe. Dann kann beim Einfügen entschieden werden: gibt es schon ein linkes Kind? Ja, dann wird das bisherige linke Kind zum Geschwisterchen des einzufügenden Knotens. Der einzufügende Knoten wird zum linken Kind.

 

[Kirby.exe]

Geschwisterchen, ja. Die Wurzelknoten eins Pairing Heaps haben keine Geschwister sondern nur linke Kinder, wenn ich es richtig verstehe. Dann kann beim Einfügen entschieden werden: gibt es schon ein linkes Kind? Ja, dann wird das bisherige linke Kind zum Geschwisterchen des einzufügenden Knotens. Der einzufügende Knoten wird zum linken Kind.

Alright Danke

 

[Kirby.exe]

Wie suche ich nun effektiv nach dem Knoten xD Mich verwirrt der ganze Stuff total

 

[mihe7]

Der gesuchte Knoten findet sich ganz oben und heißt Wurzel.

 

[Kirby.exe]

Der gesuchte Knoten findet sich ganz oben und heißt Wurzel.

Hää aber warum gibt es dann eine Fall unterscheidung? Also man soll doch prüfen ob der Knoten die Wurzel ist, wenn ja dann muss die minHeap Eigenschaft wieder hergestellt werden, ansonsten wird der Knoten incl. Teilbaum abgeschnitten und mit dem vorherigen Baum gemerged oder nicht?

 

[mihe7]

Ach so, Du bist noch beim Einfügen. Du erstellst einfach einen neuen Heap mit einem Knoten und mergst diesen mit dem bestehenden Heap. Fertig.

Hier https://www.geeksforgeeks.org/pairing-heap/ ist das noch mal etwas anschaulicher beschrieben.

 

[Kirby.exe]

Nene ich meine schon decreaseKey() xD



Ich muss ja irgenwie den Heap nach dem node mit meinem Value durchsuchen und dann decrease Key anwende xD

 

[mihe7]

Nö, die Suche ist da nicht eingeschlossen. Das x kennzeichnet den Knoten, dessen Schlüssel verringert werden soll. Lies dazu auch mal den ersten Absatz auf S. 112.

 

[Kirby.exe]

Wtf das ist sau verwirrend xD

 

[Kirby.exe]

Alsoooo ich habe jetzt einfach mal beim Prof nachgefragt, wie dieser sich dass den vorstellt xD Er meint, dass wir die HeapNodes als normalen Heap linken sollen (also so wie ich es gemacht habe) und damit man in O(1) jede Node im Heap findet, verwendet man zusätzlich ein Array der Länge n für n Zahlen da man ja 1 - n Knoten eines Graphen verwalten möchte Jetzt sollte ich den Rest hinkriegen Danke für eure Hilfe

 

[mihe7]

Da darf man auf die Lösung gespannt sein

 

[Kirby.exe]

Da darf man auf die Lösung gespannt sein

Für mein kleines Beispiel mit 4 Knoten geht es xD Und er berechnet die minimalen Kantenkosten korrekt, aber ich habe glaube ich noch einen Fehler in der Methode in decreaseKey()

 

[Kirby.exe]

Also ich bekomme bei einer großen Instanz von > 300000 Knoten einen StackOverflow....
Ich vermute es liegt an den Fällen, wenn der Knoten bei welchem die Priorität geändert werden soll die Wurzel ist und irgendein rightSibling...Oder ich habe einfach einen Fall übersehen
hier ist mein Pairing Tree:

public class PairingHeap {
    
    private HeapNode minNode;
    private HeapNode [] nodes;

    public PairingHeap(int numOfNodes) {
        minNode = null;
        nodes = new HeapNode[numOfNodes+1];       
    }
    
    public void insert(int item, int priority) {
        HeapNode node = new HeapNode(item, priority, null, null);
        minNode = merge(minNode, node);
        nodes[item] = node;
    }
    
    private HeapNode merge(HeapNode a, HeapNode b)  {
        if(a == null) {
            return b; 
        }
        if(b == null) {
            return a;
        }
        
        if(a.key < b.key) {                   
            a.addChild(b); 
            return a;         
        }
        else {
            b.addChild(a);
            return b;
        }
    }
    
    public void decreaseKey(int item, int newPriority) {
        HeapNode curr = nodes[item];
        
        if(curr == null) {
            System.out.println("This Node doesn't exist!");
            return;
        }
        curr.key = newPriority;
        
        if(curr.parent != null && curr.key < curr.parent.key) {
            if(curr.parent.leftChild != null && curr.parent.leftChild.item == curr.item) {
                //Case Decreased Node is LeftChild of Parent
                curr.parent.leftChild = curr.parent.leftChild.rightSibling;
            }else {
                //Case Decrease Node is some Right Sibling
                HeapNode temp = curr.parent.leftChild;
                while(temp != null && temp.rightSibling != null && temp.rightSibling.item != curr.item){
                    temp = temp.rightSibling;
                }
                if(temp != null) {
                    temp.rightSibling = temp.rightSibling.rightSibling;
                }
                
                
            }
            minNode = merge(minNode, curr);
            return;
        }
        // Case Decreases Node is root
        
        minNode = mergeTwoPairNodes(minNode);
    }
    
    public int findMin() {
        return minNode == null ? -1 : minNode.item;
    }
    
    public int deleteMin(){
        HeapNode result = minNode;
        minNode = mergeTwoPairNodes(minNode.leftChild);
        
        if(minNode != null) minNode.parent = null;
        return result == null ? -1 : result.item;
    }
    
    private HeapNode mergeTwoPairNodes(HeapNode node) {
        if(node == null || node.rightSibling == null) {
            return node;
        }else {
            HeapNode a = node;
            HeapNode b = node.rightSibling;
            HeapNode newNode = node.rightSibling.rightSibling;
      
            a.rightSibling = null;
            b.rightSibling = null;
      
            return merge(merge(a, b), mergeTwoPairNodes(newNode));
        }
    }
    
}

class HeapNode{
    
    public int item;
    public int key;
    public HeapNode leftChild;
    public HeapNode rightSibling;
    public HeapNode parent;
    
    public HeapNode(int item, int key, HeapNode leftChild, HeapNode parent) {
        this.item = item;
        this.key = key;
        this.leftChild = leftChild;
        this.rightSibling = null;
        this.parent = parent;
    }
    
    public void addChild(HeapNode node) {
        if(leftChild == null) {
            leftChild = node;
            node.parent = this;
            return;
        }
        
        if(leftChild.rightSibling == null) {
            leftChild.rightSibling = node;
            node.parent = this;
            return;
        }
        
        HeapNode temp = leftChild;
        while(temp.rightSibling != null) {
            temp = temp.rightSibling;
        }
        
        if(temp != null) {
            temp.rightSibling = node;
            node.parent = this;
        }
    }
    
    public String toString() {
        return "(Item: " + item + ", Key: " + key + ")";
    }
}