## algorithms – Union-Find using Fibonacci Heaps

I am trying to do a MST algorithm implementation (Finding minimum spanning tree by extracting minimum edges and including every vertex) using Fibonacci Heaps. I want to minimize the time complexity by augmenting data structure if needed.

Approximate Algorithm :

``````MST(G)
2 T ← {} // set that will store the edges of the MST
3 for i ← 1..n
4 Vi ← {i}
5 Ei ← {(i, j) : j is a vertex and (i, j) is an edge of G} // set of all edges incident with vertex i
6 end for
7 while there is more than one set Vi
8 choose any Vi
9 extract minimum weight edge (u, v) from Ei
10 one of the endpoints u of this edge is in Vi. let Vj be the set that contains the other endpoint v
11 if i != j then
12 T ← T ∪ {(u, v)}
13 combine Vi and Vj into Vi (destroying Vj )
14 combine Ei and Ej into Ei (destroying Ej )
15 end if
16 end while
17 return T
18 end MST

``````

Time complexity Analysis Approach:

The for loop of line 3 − 5 requires O(V) MAKE-HEAP operations and a total of O(E) INSERT
operations in line 5. Note that the size of each Ei set can be at most O(V) by definition. The
total time is thus O(V + E) ~ O(E) (Because Fibonacci Heaps can support constant insertions for both MakeHeap and Insertions.

Now for Line 7-15
– We can at most extract O(E) edges in line 9 taking a total of (E lg V) time if after every insert we also consolidate. (Debatable) Can we use consolidate a bit more efficiently?

Also, I feel that we are doing a couple of Union operations further. How to optimize it in a way that I try to save maximum time by using some auxiliary data structures if possible.

Posted on Categories Articles

## Does the heap property in the definition of binary heaps apply recursively?

The definition of `binary heaps` says that it should be a complete binary tree and it should follow the heap property where according to the heap property, the key stored in each node is either greater than or equal to or less than or equal to the keys in the node’s children. In the above tree, the node with value 70 is greater than its parent 10 breaking the heap property. However, 70 is also greater than 40 and lies in the subtree of 40. Will we say that the heap property is also breaking at 40, even though 40 is greater than its two children 10 and 2?

Posted on Categories Articles

## heaps – Java Implementation of PriorityQueue supporting priority updates

I’ve coded up an implementation of MinPriorityQueue in java using a hashMap to store the indices of the elements in my heap. I require such an implementation for Prim’s and Dijkstra’s algorithm, while this implementation works for most test cases upto 200 nodes, I’m getting incorrect outputs for many larger test cases. I’ve spent 2 days now trying to debug my implementation and I still have no idea why it fails.

I understand that debugging this for anyone else will also be a time consuming task.
Therefore can someone please share such an implementation in java or c++ using Hashmap (java preferably).
Because at this point it seems only looking at a correct implementation could help me fix my code.

Also, I’m under the impression that such an implementation using hashmap is common. If I’m wrong in my assumption, please tell me what is the most common implementation of a PriorityQueue for problems such as Dijkstra’s or Prim’s

Here is my implementation, in case something very obvious is missing and someone with more expertise can point out the mistake that would be most appreciated.

``````import java.util.HashMap;
import java.util.NoSuchElementException;

public class Heap<Key extends Comparable<Key>> {
private Key() heap;
private int maxN, n;
private HashMap<Key, Integer> map;
@SuppressWarnings("unchecked")
public Heap(int maxN) {
if(maxN < 0 ) throw new IllegalArgumentException();
this.maxN = maxN;
n = 0;
heap = (Key()) new Comparable(maxN);
map = new HashMap<>(maxN);
}

boolean isEmpty() {
return n == 0;
}

boolean insert(Key e) {
if(n +1 > maxN) throw new IllegalArgumentException("maximum capacity reached " + maxN);
heap(n) = e;
map.put(e,n);
int i = n++;
while ( (i+1)/2 - 1 >= 0){
if ( e.compareTo(heap((i+1)/2 - 1)) < 0 ) {
swap(i, (i+1)/2 - 1);
i = (i+1)/2 - 1;
}
else
break;
}
return true;
}

Key extractMin() {
if(n == 0) throw new NoSuchElementException("Priority queue underflow ");
Key min = heap(0);
swap(0, n-1);
map.remove(min);
n--;
int j = 0, s;
while(j <= (n/2)-1){
if(j == (n/2)-1 && n == (j+1)*2 )
s = (j+1)*2 - 1;
else
s = heap((j+1)*2 - 1).compareTo(heap((j+1)*2)) < 0 ? (j+1)*2 - 1 : (j+1)*2;
if(heap(j).compareTo(heap(s)) > 0 ){
swap(j, s);
j = s;
}
else break;
}
return min;
}

Key delete(Key e){
if(!map.containsKey(e)) throw new NoSuchElementException(e+"does not exist ");
int j = map.get(e), s;
Key del = e;
swap(j, n-1);
map.remove(e);
n--;
while( j <= n/2 - 1){
if(j == (n/2)-1 && n == (j+1)*2)
s = (j+1)*2 - 1;
else
s = heap((j+1)*2 - 1).compareTo(heap((j+1)*2)) < 0 ? (j+1)*2 - 1 : (j+1)*2;
if(heap(j).compareTo(heap(s)) > 0 ){
swap(j, s);
j = s;
}
else break;
}
return del;
}

boolean decreasePriority(Key e){
if(n == 0)
return insert(e);
if(map.containsKey(e))
delete(e);
return insert(e);
}

private void swap(int i, int j) {
Key t = heap(i);
heap(i) = heap(j);
heap(j) = t;
map.replace(heap(i), i);
map.replace(heap(j), j);
}

@Override
public String toString() {
String res = "(";
int i;
for (i = 0; i < n-1; i++){
res += heap(i) + ", ";
}
res += heap(i)+")";
return res;
}
}
``````

Posted on Categories Articles

## Data structures – use of stacks and heaps in object-oriented programming. Reasons?

In object-oriented programming, heaps are used to store the actual objects. Batches are used to store reference variables for the objects.

What are the specific reasons for choosing these two specific data structures?

What is the benefit of a bunch in the scenario described? What are the benefits of a stack?

Posted on Categories Articles

## Algorithms – Distinct Binary Heaps

I have $$n$$ Elements off $$n-1$$ are different. The repeated element is either the minimum or the maximum element. I have to find out how many different clusters can be made from it.

My analysis : I started with $$n$$ different elements. Since the root is solid (maximum or minimum element), we can choose $$l$$(Determined by subtracting the total number of elements from the elements on the penultimate level.) $$n-1$$ Elements and select recursively for the left subtree and the right subtree.

Repeat Relationship:

$$T (n) = {n-1 choose l} * T (l) * T (r)$$

Now for $$n-1$$ different elements (given), for root we have $$2$$ Options, d. H. maximum elements, and we can proceed recursively as above for the left and right subtree. But since the repeated element is there as well, I can not figure out exactly how to do it.

e.g: $$A = (2,6,6)$$ =>
There are 2 different heaps.

I can not imagine how I can determine the number of heaps in this case. Can anyone think of algorithm / repetition relation to find something like that?

Posted on Categories Articles