COIN-OR::LEMON - Graph Library

Changeset 39:28b0d751d29f in lemon-0.x for src


Ignore:
Timestamp:
01/27/04 22:23:33 (21 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@53
Message:

Alap leiras a BinHeap? -rol

BinHeap::state() befejezese

Location:
src
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/include/bin_heap.hh

    r37 r39  
     1/* FIXME: Copyright ...
     2 *
     3 * This implementation is heavily based on STL's heap functions and
     4 * the similar class by Alpar Juttner in IKTA...
     5 */
     6
     7/******
     8 *
     9 * BinHeap<KeyType, ValueType, KeyIntMap, [ValueCompare]>
     10 *
     11 * Ez az osztaly kulcs-ertek parok tarolasara alkalmas binaris kupacot
     12 * valosit meg.
     13 * A kupacban legfolul mindig az a par talalhato, amiben az _ertek_ a
     14 * legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz
     15 * lett keszitve...)
     16 *
     17 * Megjegyzes: egy kicsit gyanus nekem, hogy a kupacos temakorben nem
     18 * azt hivjak kulcsnak, amit most en annak nevezek. :) En olyan
     19 * property_map -os ertelemben hasznalom.
     20 *
     21 * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami
     22 * a kulcsokhoz egy int-et tud tarolni (ezzel tudom megkeresni az illeto
     23 * elemet a kupacban a csokkentes es hasonlo muveletekhez).
     24 * A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek
     25 * is elnie kell. (???)
     26 *
     27 * Ketfele modon hasznalhato:
     28 * Lusta mod:
     29 * put(Key, Value) metodussal pakolunk a kupacba,
     30 * aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor
     31 * csokkentettunk-e rajta, vagy noveltunk.
     32 * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
     33 * minden szobajovo kulcs ertekre, -1 -es ertekkel!
     34 * Es ilyen esetben a kulcsokrol lekerdezheto az allapotuk a state metodussal:
     35 * (nem jart meg a kupacban PRE_HEAP=-1, epp a kupacban van IN_HEAP=0,
     36 *  mar kikerult a kupacbol POST_HEAP=-2).
     37 * Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak
     38 * meg meg tudja mondani a "legkisebb" erteku elemet. De csak nagyjabol,
     39 * hiszen a kupacbol kikerult elemeknek elvesz az ertekuk...
     40 *
     41 * Kozvetlen mod:
     42 * push(Key, Value) metodussal belerakunk a kupacba (ha az illeto kulcs mar
     43 * benn volt, akkor gaz).
     44 * increase/decrease(Key k, Value new_value) metodusokkal lehet
     45 * novelni/csokkenteni az illeto kulcshoz tartozo erteket. (Ha nem volt meg
     46 * benne a kupacban az illeto kulcs, vagy nem abba az iranyba valtoztattad
     47 * az erteket, amerre mondtad -- gaz).
     48 *
     49 * Termeszetesen a fenti ket modot ertelemszeruen lehet keverni.
     50 * Ja es mindig nagyon gaz, ha belepiszkalsz a map-be, amit a kupac
     51 * hasznal. :-))
     52 *
     53 *
     54 * Bocs, most faradt vagyok, majd egyszer leforditom. (Misi)
     55 *
     56 */
     57
     58
    159#ifndef BIN_HEAP_HH
    260#define BIN_HEAP_HH
     
    2886     * PRE_HEAP (-1) to any element to be put in the heap...
    2987     */
    30 
    31     enum state {
     88    enum state_enum {
    3289      IN_HEAP = 0,
    3390      PRE_HEAP = -1,
     
    83140    void pop() {
    84141      int n = data.size()-1;
    85       if ( n>0 ) {
    86         bubble_down(0, data[n], n);
    87       }
    88       if ( n>=0 ) {
     142      if( n>=0 ) {
     143        kim.put(data[0].first, POST_HEAP);
     144        if ( n>0 ) {
     145          bubble_down(0, data[n], n);
     146        }
    89147        data.pop_back();
    90148      }
     
    115173      int idx = kim.get(k);
    116174      bubble_down(idx, PairType(k,v), data.size());
     175    }
     176
     177    state_enum state(const Key &k) const {
     178      int s = kim.get(k);
     179      if( s>=0 )
     180        s=0;
     181      return state_enum(s);
    117182    }
    118183
  • src/work/bin_heap_demo.cc

    r37 r39  
    99class string_int_map;
    1010
     11// Egy binaris kupac, ami stringekhez rendelt double ertekeket tarol,
     12// azaz mindig az a string van a tetejen, amihez a legkisebb szam tartozik.
     13// A kupac egy string_int_map tipusu property_map segitsegevel tarolja
     14// a stringek aktualis helyet sajatmagan belul.
     15// Egy olyan stringhez, ami meg nincsen a kupac -1 -et kell rendelnunk.
    1116typedef BinHeap<string, double, string_int_map> StrDoubleHeap;
    1217
     
    7984       << heap.topValue() << endl;
    8085
     86  cout << "heap.state(\"szilva\") = "
     87       << heap.state("szilva") << endl;
     88  cout << "heap.put(\"szilva\", 0.5);\n";
     89  heap.put("szilva", 0.5);
     90  cout << "heap.state(\"szilva\") = "
     91       << heap.state("szilva") << endl;
     92  cout << "heap.top() = "
     93       << heap.top() << endl;
     94  cout << "heap.pop();\n";
     95  heap.pop();
     96  cout << "heap.state(\"szilva\") = "
     97       << heap.state("szilva") << endl;
     98
    8199  cout << "heap.size() = "
    82100       << heap.size() << endl;
     
    89107       << (heap.empty()?"true":"false") << endl; 
    90108}
    91 
Note: See TracChangeset for help on using the changeset viewer.