• Wir präsentieren Dir heute ein Stellenangebot für einen Java Entwickler - m/w/d in Augsburg, München, Stuttgart oder Bamberg. Hier geht es zur Jobanzeige

Pairing Heaps

Kirby.exe

Kirby.exe

Top Contributor
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?
 
Kirby.exe

Kirby.exe

Top Contributor
Ich zerbreche mir gerade den Kopf über decreaseKey() und sehe nicht so richtig wie ich das implementieren könnte...Hier ist mein bisheriger PairingHeap:
Java:
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);
    }
}
 
Kirby.exe

Kirby.exe

Top Contributor
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

mihe7

Top Contributor
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

Kirby.exe

Top Contributor
Also ich habe die Implementation von HeapNode nun wie folgt:

Java:
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:

Java:
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
 
Zuletzt bearbeitet:
mihe7

mihe7

Top Contributor
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

Kirby.exe

Top Contributor
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

Kirby.exe

Top Contributor
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?
 
Kirby.exe

Kirby.exe

Top Contributor
Nene ich meine schon decreaseKey() xD

Bildschirmfoto 2021-01-20 um 13.15.25.png


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

mihe7

Top Contributor
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

Kirby.exe

Top Contributor
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 :)
 
Kirby.exe

Kirby.exe

Top Contributor
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:

Java:
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 + ")";
    }
}
 
Anzeige

Neue Themen


Oben