Binomiální halda
Binomiální halda (Binomial heap) je halda složená z lesa binomiálních stromů. Každý prvek každého stromu má vyšší prioritu, než kterýkoliv z jeho potomků – halda se proto chová jako prioritní fronta. Binomiální halda má oproti binární a d-regulární haldě výhodu v rychlejších operacích sloučení hald () a vložení prvku (amortizovaně
).
Binomiální strom
Binonomiální strom řádu 0 obsahuje právě jeden uzel. Binomiální strom řádu n vznikne sloučením dvou stromů řádu takovým způsobem, že porovnáme prioritu kořenů obou stromů a následně ten s nižší prioritou zavěsíme pod kořen s vyšší prioritou. Binomiální halda obsahuje maximálně jeden strom každého řádu.
- Binomiální strom řádu n obsahuje
uzlů.
- Binomiální strom řádu n má hloubku n.
- Kořen binomiální stromu má n potomků.
- Kořen binomiálního stromu obsahuje jako své potomky všechny stromy nižších řádů.
Základní operace binomiální haldy
Operace jsou popsány pro min-heap – nižší prvek má vyšší prioritu. Max-heap (tj. vyšší prvek má vyšši prioritu) funguje analogicky.
Insert
Vloží prvek do haldy. Vytvoří pro prvek binomiální strom řádu 0 a provede sloučení tohoto stromu s haldou. Pokud vkládáme prvek s nižší prioritou, než je priorita současného nejnižšího prvku haldy, tak tento prvek označíme za minimální. Asymptotická složitost operace je , amortizovaná složitost
.
Return top
Vrátí a smaže z haldy prvek s nejvyšší prioritou. Odebere minimální prvek haldy, všechny podstromy přidá zpět do haldy prostřednictvím operace merge. Nalezne nový nejnižší prvek průchodem přes všechny kořeny binomiálních stromů. Asymptotická složitost operace je .
Merge
Provede sloučení haldy B do haldy A. Tato operace odpovídá sčítání dvou binárních čísel. Algoritmus prochází obě haldy od nejnižšího řádu, pokud halda B obsahuje strom řádu n a halda A nikoliv, pak jej pouze překopíruje. Pokud obě haldy obsahují stromy stejného řádu, tak je sloučí do přenosového stromu (obdoba přenosového bitu u sčítání), který zohlední pří následném spojování stromů řádu . Nakonec porovná minimální prvky obou slučovaných hald a za minimální prvek výsledné haldy označí nižší z nich. Asymptotická složitost operace je
.
Kód
/**
* Binomialni halda
* Radi prvky dle priority (mensi == vyssi priorita)
* @author Pavel Micka
*/
public class BinomialHeap<ENTITY extends Comparable> {
private Node<ENTITY>[] nodes;
private Node<ENTITY> min;
/**
* Konstruktor
* @param capacity kapacita haldy
*/
public BinomialHeap(int capacity) {
min = null;
nodes = new Node[((int) (Math.log(capacity) / Math.log(2))) + 2];
}
/**
* Vlozi prvek do haldy, pokud je mensi nez aktualni minimalni, tak
* jej ulozi jako nejmensi prvek
* @param e
*/
public void insert(ENTITY e) {
Node<ENTITY> n = new Node<ENTITY>(e);
if (nodes[0] != null) merge(n, nodes[0]);
else nodes[0] = n;
if (min == null) min = n;
else if (min.value.compareTo(n.value) == 1) min = n;
}
/**
* Smaze a vrati entitu s nejvyssi prioritou
* @return entita s nejvyssi prioritou, @null, pokud je halda prazdna
*/
public ENTITY returnTop() {
if(min == null) return null;
ENTITY tmp = min.value;
nodes[min.order] = null; //strom vyjmeme
for (Node n : min.children) { //a z potomku udelame nove stromu
n.parent = null;
if(nodes[n.order] != null) merge(n, nodes[n.order]);
else nodes[n.order] = n;
}
min.children.clear();
ENTITY minVal = null;
Node minNode = null;
for(int i = 0; i < nodes.length; i++){
if(nodes[i] != null){
if(minVal == null){
minVal = nodes[i].value;
minNode = nodes[i];
}
else if(minVal.compareTo(nodes[i].value) == 1){
minVal = nodes[i].value;
minNode = nodes[i];
}
}
}
min = minNode;
return tmp;
}
/**
* Slouci haldy, pokud mergovana halda obsahuje mensi prvek, nez halda, na
* ktere je volana operace, pak je tento prvek minimalni i ve sloucene halde
* @param heap
*/
public void mergeHeaps(BinomialHeap<ENTITY> heap) {
Node<ENTITY> carry = null;
for (int i = 0; i < heap.nodes.length; i++) {
if(nodes[i] == null){
if(heap.nodes[i] == null){
nodes[i] = carry;
carry = null;
}else{
if(carry == null){
nodes[i] = heap.nodes[i];
}else{
carry = mergeTrees(heap.nodes[i], carry);
}
}
}else{
if(heap.nodes[i] == null){
if(carry != null){
carry = mergeTrees(nodes[i], carry);
nodes[i] = null;
}
}else{
if(carry == null){
carry = mergeTrees(nodes[i], heap.nodes[i]);
nodes[i] = null;
}else{
carry = mergeTrees(carry, heap.nodes[i]);
}
}
}
}
if(carry != null) throw new RuntimeException("Preteceni haldy (halda je preplnena)");
if (this.min == null) this.min = heap.min;
else if(this.min != null && heap.min != null && heap.min.value.compareTo(min.value) == -1) min = heap.min;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
for(int i = 0; i < nodes.length; i++){
if(nodes[i] == null) builder.append(i + ": null\\n");
else builder.append(i + ":\\n" + nodes[i].toString() + "\\n");
}
return builder.toString();
}
/**
* Provede slouceni binomialnich stromu (vcetne preteceni do vyssich radu)
* @param a
* @param b
*/
private void merge(Node a, Node b) {
if (a.order != b.order)
throw new IllegalArgumentException("Stromy nejsou stejneho radu");
int tmpOrder = a.order;
nodes[tmpOrder] = null;
Node newRoot = null;
newRoot = mergeTrees(a, b);
if (nodes[tmpOrder + 1] == null) nodes[tmpOrder + 1] = newRoot;
else merge(newRoot, nodes[tmpOrder + 1]);
}
/**
* Slouci binomialni stromy v jeden (zavesi strom s nizsi prioritou pod strom
* s vyssi prioritou)
* @param a strom a
* @param b strom b
* @return
*/
private Node mergeTrees(Node a, Node b) {
Node newRoot = null;
if (a.value.compareTo(b.value) < 0) {
b.parent = a;
a.children.add(b);
a.order++;
newRoot = a;
} else {
a.parent = b;
b.children.add(a);
b.order++;
newRoot = b;
}
return newRoot;
}
/**
* Reprezentuje uzel binomialni haldy
* @param <ENTITY>
*/
private class Node<ENTITY extends Comparable> {
Node<ENTITY> parent;
ENTITY value;
List<Node> children;
int order; //rad binomialni haldy
public Node(ENTITY value) {
this.value = value;
children = new ArrayList<Node>();
order = 0;
}
@Override
public String toString() {
String s = "Node value: " + value + ", order: " + order + "\\n";
for(Node n : children){
s += n.toString();
}
return s;
}
}
}