## HEAP

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
Phantom
Posts: 58
Joined: 8 years ago
Location: Cuba
Gender:

### HEAP

Here is my implementation of a HEAP in Python. You can post your implementation in another language or… if you want… A Fibonacci HEAP!! My HEAP is the normal HEAP…:

Code: Select all

``````class Heap:
----def __init__(self):
--------self.Values, self.Count = [], 0

----def __HeapifyTop(self, pos):
--------fatherPos = int((pos - 1) / 2)
--------while pos and cmp(self.Values[fatherPos], self.Values[pos]) > 0:
------------self.Values[fatherPos], self.Values[pos] = self.Values[pos], self.Values[fatherPos]
------------pos, fatherPos = fatherPos, int((fatherPos - 1) / 2)

----def __HeapifyBelow(self, pos):
--------trickle = True
--------while trickle:
------------actP, trickle = 2 * pos + 1, False
------------minVal = (self.Values[actP], actP) if actP < len(self.Values) else None
------------if minVal:
----------------actP += 1
----------------minVal = min((self.Values[actP], actP) if actP < len(self.Values) else minVal, minVal)
----------------if cmp(self.Values[pos], minVal[0]) > 0:
--------------------trickle = True
--------------------self.Values[pos], self.Values[minVal[1]] = self.Values[minVal[1]], self.Values[pos]
--------------------pos = minVal[1]

----def Insert(self, val):
--------pos = len(self.Values)
--------self.Values.append(val)
--------self.Count += 1
--------self.Heapify(pos)

----def SupMin(self):
--------res = self.Values[0]
--------act = self.Values.pop()
--------if self.Values:
------------self.Values[0] = act
------------self.Heapify(0)
--------self.Count -= 1
--------return res

----def Heapify(self, pos):
--------self.__HeapifyTop(pos)
--------self.__HeapifyBelow(pos)``````

xshaka
Posts: 10
Joined: 8 years ago
Gender:

### Re: HEAP

Typically in ACM-ICPC style contests, you won't need nothing beyond a "normal" heap. Fibonacci heaps are a very weird data structure which I've seen used rarely just to make Djkstra algorithm extra fast for some online judges problems where it was required. Here you have my solution for http://www.spoj.pl/problems/SHPATH using it:

Code: Select all

``````//============================================================================
// Name        : Shortest_Path.cpp
// Author      : Shaka
// Version     :
// Description : Hello World in C++, Ansi-style
//============================================================================

#define MAXN 10000
#include <cstdlib>
#include <map>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
class FHeapNode {
public:
FHeapNode *parent;
FHeapNode *left, *right;
FHeapNode *child;
int rank;
int marked;
int key;
int item;
};

class FHeap {
public:
FHeap(int n) {
int i;
maxTrees = 1 + (int)(1.44 * log(n)/log(2.0));
maxNodes = n;

trees = new FHeapNode*[maxTrees];
for (i = 0; i < maxTrees; i++)
trees[i] =0;

nodes = new FHeapNode*[n];
for (i = 0; i < n; i++)
nodes[i] = 0;

itemCount = 0;
treeSum = 0;
compCount = 0;
}
~FHeap() {
int i;
for (i = 0; i < maxNodes; i++)
delete nodes[i];
delete [] nodes;
delete [] trees;
}

int deleteMin() {
FHeapNode *minNode, *child, *next;
int k, k2;
int r, v, item;
v = treeSum;
r = -1;
while (v) {
v >>= 1;
r++;
};
minNode = trees[r];
k = minNode->key;
while (r > 0) {
r--;
next = trees[r];
if (next) {
if ((k2 = next->key) < k) {
k = k2;
minNode = next;
}
compCount++;
}
}
r = minNode->rank;
trees[r] = NULL;
treeSum -= (1 << r);
child = minNode->child;
if (child)
meld(child);
item = minNode->item;
nodes[item] = NULL;
delete minNode;
itemCount--;
return item;
}
void insert(int item, int k) {
FHeapNode *newNode;
newNode = new FHeapNode;
newNode->child = NULL;
newNode->left = newNode->right = newNode;
newNode->rank = 0;
newNode->item = item;
newNode->key = k;
nodes[item] = newNode;
meld(newNode);
itemCount++;
}
void decreaseKey(int item, int newValue) {
FHeapNode *cutNode, *parent, *newRoots, *r, *l;
int prevRank;
cutNode = nodes[item];
parent = cutNode->parent;
cutNode->key = newValue;
if (!parent) {
return;
}
l = cutNode->left;
r = cutNode->right;
l->right = r;
r->left = l;
cutNode->left = cutNode->right = cutNode;
newRoots = cutNode;
while (parent && parent->marked) {
parent->rank--;
if (parent->rank) {
if (parent->child == cutNode)
parent->child = r;
} else {
parent->child = NULL;
}
cutNode = parent;
parent = cutNode->parent;
l = cutNode->left;
r = cutNode->right;
l->right = r;
r->left = l;
l = newRoots->left;
newRoots->left = l->right = cutNode;
cutNode->left = l;
cutNode->right = newRoots;
newRoots = cutNode;
}
if (!parent) {
prevRank = cutNode->rank + 1;
trees[prevRank] = NULL;
treeSum -= (1 << prevRank);
} else {
parent->rank--;
if (parent->rank) {
if (parent->child == cutNode)
parent->child = r;
} else {
parent->child = NULL;
}
parent->marked = 1;
}
meld(newRoots);
}
int nItems() const {
return itemCount;
}

long nComps() const {
return compCount;
}
void dump() const;

private:
FHeapNode **trees;
FHeapNode **nodes;
int maxNodes, maxTrees, itemCount, treeSum;
long compCount;

void meld(FHeapNode *treeList) {
FHeapNode *first, *next, *nodePtr, *newRoot, *temp, *temp2, *lc, *rc;
int r;
nodePtr = first = treeList;
do {
next = nodePtr->right;
nodePtr->right = nodePtr->left = nodePtr;
nodePtr->parent = NULL;
newRoot = nodePtr;
r = nodePtr->rank;
do {
if ((temp = trees[r])) {
trees[r] = NULL;
treeSum -= (1 << r);
if (temp->key < newRoot->key) {
temp2 = newRoot;
newRoot = temp;
temp = temp2;
}
compCount++;
if (r++ > 0) {
rc = newRoot->child;
lc = rc->left;
temp->left = lc;
temp->right = rc;
lc->right = rc->left = temp;
}
newRoot->child = temp;
newRoot->rank = r;
temp->parent = newRoot;
temp->marked = 0;
} else {
trees[r] = newRoot;
treeSum += (1 << r);
newRoot->marked = 1;
}
} while (temp);
nodePtr = next;
} while (nodePtr != first);
}
};
pair<int,int> points[MAXN];
bool s[MAXN];
bool f[MAXN];
int distances[MAXN];
FHeap *hd;
int main() {
register int cas, N, W, i, u, v, r, j, dist;
scanf("%d", &cas);
while (cas--) {
scanf("%d", &N);
map<string, int> hashed;
for (i = 0; i < N; i++) {
string name;
cin >> name;
hashed[name] = i;
scanf("%d", &W);
for (int j = 0; j < W; j++) {
scanf("%d%d", &u, &v);
u--;
}
}
scanf("%d", &r);
while (r--) {
hd = new FHeap(N);
string name1, name2;
cin >> name1 >> name2;
u = hashed[name1];
v = hashed[name2];
memset(s, false, N);
memset(f, false, N);
for (int i = 0; i < N; i++)
distances[i] = 200000;
distances[u] = 0;
hd->insert(u, 0);
f[u] = true;
while (hd->nItems() > 0 && !s[v]) {
u = hd->deleteMin();
s[u] = true;
f[u] = false;
j = (*it).first;
if (!s[j]) {
dist = distances[u] + (*it).second;
if (distances[j] > dist) {
distances[j] = dist;
if (f[j])
hd->decreaseKey(j, dist);
else {
hd->insert(j, dist);
f[j] = true;
}
}
}
it++;
}
}
printf("%d\n", distances[v]);
}
}
return 0;
}``````