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.
User avatar
Phantom
Posts: 58
Joined: Thu Nov 17, 2011 11:21 am
Location: Cuba
Gender: None specified

HEAP

Postby Phantom » Sun Jun 03, 2012 11:50 pm

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)



User avatar
xshaka
Posts: 10
Joined: Tue Feb 14, 2012 1:29 pm
Gender: None specified

Re: HEAP

Postby xshaka » Sat Sep 15, 2012 10:46 am

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     :
// Copyright   : Your copyright notice
// 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);
   }
};
vector<pair<int,int> > ady[MAXN];
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;
         ady[i].clear();
         scanf("%d", &W);
         for (int j = 0; j < W; j++) {
            scanf("%d%d", &u, &v);
            u--;
            ady[i].push_back(make_pair(u, v));
         }
      }
      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;
            vector<pair<int,int> >::iterator it = ady[u].begin();
            while (it != ady[u].end()) {
               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;
}


Return to “Algorithms”

Who is online

Users browsing this forum: No registered users and 1 guest