Arndt - Algorithms for Programmers (523138), страница 38
Текст из файла (страница 38)
DATA STRUCTURES}217if ( 0==n_ ) return 0;--lpos_;if ( lpos_ == -1UL ) lpos_ = s_ - 1;z = x_[lpos_];--n_;return n_ + 1;ulong read_first(Type & z) const// read (but don’t remove) first entry// return number of elements (i.e. on error return zero){if ( 0==n_ ) return 0;z = x_[fpos_];return n_;}ulong read_last(Type & z) const// read (but don’t remove) last entry// return number of elements (i.e. on error return zero){return read(n_-1, z); // ok for n_==0}ulong read(ulong k, Type & z) const// read entry k (that is, [(fpos_ + k)%s_])// return 0 if k>=n_// else return k+1{if ( k>=n_ ) return 0;ulong j = fpos_ + k;if ( j>=s_ ) j -= s_;z = x_[j];return k + 1;}private:void grow(){ulong ns = s_ + gq_; // new sizeType *nx = new Type[ns];// move read-position to zero:// rotate_left(x_, s_, fpos_); copy(x_, nx, s_);copy_cyclic(x_, nx, s_, fpos_);fpos_ = 0;lpos_ = n_;delete [] x_; x_ = nx;s_ = ns;}};Its working is demonstrated in [FXT: file demo/deque-out.txt]:insert_first( 1)insert_last(51)insert_first( 2)insert_last(52)insert_first( 3)insert_last(53)insert_first( 4)insert_last(54)extract_first()= 4extract_last() =54insert_first( 5)insert_last(55)extract_first()= 5extract_last() =55extract_first()= 3extract_last() =53extract_first()= 2extract_last() =52insert_first( 6)insert_last(56)extract_first()= 6extract_last() =56extract_first()= 1112233443355332211661151511122332233221151511151515151112211221151515252515111515111515152525151 565652525151525251515252535352525353525253535353 54545353 5555CHAPTER 10.
DATA STRUCTURESextract_last() =51(dequeue empty)(dequeue empty)insert_first( 7)insert_last(57)extract_first()= 7extract_last() =57(dequeue empty)(dequeue empty)insert_first( 9)insert_last(59)10.521877 575799 59Heap and priority queueA heap is a binary tree where the left and right children are smaller or equal than their parent node. Thefunctiontemplate <typename Type>ulong test_heap(const Type *x, ulong n)// return 0 if x[] has heap property// else index of node found to be bigger than its parent{const Type *p = x - 1;for (ulong k=n; k>1; --k){ulong t = (k>>1); // parent(k)if ( p[t]<p[k] ) return k;}return 0; // has heap property}finds out whether a given array has the described heap-property.It turns out that a unordered array of size n can be reordered to a heap in O(n) time1 . The routinetemplate <typename Type>void build_heap(Type *x, ulong n)// reorder data to a heap{for (ulong j=(n>>1); j>0; --j)}heapify1(x-1, n, j);does the trick.
It uses the subroutinetemplate <typename Type>void heapify1(Type *z, ulong n, ulong k)// subject to the condition that the trees below the children of node// k are heaps, move the element z[k] (down) until the tree below node// k is a heap.//// data expected in z[1..n] (!){ulong m = k;ulong l = (k<<1); // left(k);if ( (l <= n) && (z[l] > z[k]) ) m = l;ulong r = (k<<1) + 1; // right(k);if ( (r <= n) && (z[r] > z[m]) ) m = r;if ( m != k ){swap(z[k], z[m]);heapify1(z, n, m);}}That runs in time O(log(n)).1 Thisis slightly non-obvious, see [21] (p.145) for an explanation.CHAPTER 10. DATA STRUCTURES219Heaps are useful to build a so-called priority queue. This is a data structure that supports insertion of anelement and extraction of the maximal element it contains both in an efficient manner. A priority queuecan be used to ‘schedule’ a certain event for a given point in time and return the next pending event.A new element can be inserted into a heap in O(log(n)) time by appending it and moving it towards theroot (that is, the first element) as necessary:bool heap_insert(Type *x, ulong n, ulong s, Type t)// with x[] a heap of current size n// and max size s (i.e.
space for s elements allocated)// insert t and restore heap-property.//// Return true if successful// else (i.e. space exhausted) false//// Takes time \log(n){if ( n > s ) return false;++n;Type *x1 = x - 1;ulong j = n;while ( j > 1 ){ulong k = (j>>1); // k==parent(j)if ( x1[k] >= t ) break;x1[j] = x1[k];j = k;}x1[j] = t;return true;}Similarly, the maximal element can be removed in time O(log(n)):template <typename Type>Type heap_extract_max(Type *x, ulong n)// Return maximal element of heap and// restore heap structure.// Return value is undefined for 0==n{Type m = x[0];if ( 0 != n ){Type *x1 = x - 1;x1[1] = x1[n];--n;heapify1(x1, n, 1);}// else errorreturn m;}Two modifications seem appropriate: First, replacement of extract max() by a extract next(), leavingit as an (compile time) option whether to extract the minimal or the maximal element.
This is achievedby changing the comparison operators at a few strategic places so that the heap is built either as describedabove or with its minimum as first element:#if 1// next() is the one with the smallest key// i.e. extract_next() is extract_min()#define _CMP_ <#define _CMPEQ_ <=#else// next() is the one with the biggest key// i.e. extract_next() is extract_max()#define _CMP_ >#define _CMPEQ_ >=#endifSecond, augmenting the elements used by a event-description that can be freely defined. The resultingutility class istemplate <typename Type1, typename Type2>CHAPTER 10. DATA STRUCTURESclass priority_queue{public:Type1 *t_; // time:t[0..s-1]Type2 *e_; // events: e[0..s-1]ulong s_;// allocated size (# of elements)ulong n_;// current number of eventsulong gq_; // grow gq elements if necessary, 0 for "don’t grow"public:priority_queue(ulong n, ulong growq=0){s_ = n;t_ = new Type1[s_];e_ = new Type2[s_];n_ = 0;gq_ = growq;}~priority_queue() { delete [] t_; delete [] e_; }ulong n() const { return n_; }Type1 get_next(Type2 &e) const// No check if empty{e = e_[0];return t_[0];}void heapify1(Type1 *t1, ulong n, ulong k, Type2 *e1)// events ine1[1..n]// time of events in t1[1..n]{ulong m = k;ulong l = (k<<1); // left(k);if ( (l <= n) && (t1[l] _CMP_ t1[k]) ) m = l;ulong r = (k<<1) + 1; // right(k);if ( (r <= n) && (t1[r] _CMP_ t1[m]) ) m = r;if ( m != k ){swap(t1[k], t1[m]); swap(e1[k], e1[m]);heapify1(t1, n, m, e1);}}Type1 extract_next(Type2 &e){Type1 m = get_next(e);if ( 0 != n_ ){Type1 *t1 = t_ - 1;Type2 *e1 = e_ - 1;t1[1] = t1[n_]; e1[1] = e1[n_];--n_;heapify1(t1, n_, 1, e1);}// else errorreturn m;}bool insert(const Type1 &t, const Type2 &e)// Insert event e at time t// Return true if successful// else (i.e.
space exhausted and 0==gq_) false{if ( n_ >= s_ ){if ( 0==gq_ ) return false; // growing disabledulong ns = s_ + gq_; // new sizeType1 *nt = new Type1[ns];copy(t_, nt, s_);Type2 *ne = new Type2[ns];copy(e_, ne, s_);delete [] t_; t_ = nt;delete [] e_; e_ = ne;s_ = ns;}220CHAPTER 10.
DATA STRUCTURES};}221++n_;Type1 *t1 = t_ - 1;Type2 *e1 = e_ - 1;ulong j = n_;while ( j > 1 ){ulong k = (j>>1); // k==parent(j)if ( t1[k] _CMPEQ_ t ) break;t1[j] = t1[k]; e1[j] = e1[k];j = k;}t1[j] = t;e1[j] = e;return true;The second argument of the constructor determines the number of elements added in case of growth, itis disabled (equals zero) by default. [FXT: class priority queue in ds/priorityqueue.h]A demo that inserts events at random times 0 ≤ t < 1 and for the sake of simplicity uses the negativetime values as ‘events’ gives the outputinserting into piority_queue:...# :event @time0:-0.840188 @0.8401881:-0.394383 @0.3943832:-0.783099 @0.7830993:-0.79844 @0.798444:-0.911647 @0.9116475:-0.197551 @0.1975516:-0.335223 @0.3352237:-0.76823 @0.768238:-0.277775 @0.2777759:-0.55397 @0.55397extracting from piority_queue:...# :event @time10:-0.197551 @0.1975519:-0.277775 @0.2777758:-0.335223 @0.3352237:-0.394383 @0.3943836:-0.55397 @0.553975:-0.76823 @0.768234:-0.783099 @0.7830993:-0.79844 @0.798442:-0.840188 @0.8401881:-0.911647 @0.911647Here all events were inserted, then all were extracted, which does not quite reflect the typical use wherethe inserts and extracts occur intermixed.
[FXT: file demo/priorityqueue-demo.cc]10.6Bit-arrayThe use of bit-arrays should be obvious: an array of tag values (like ‘seen’ versus ‘unseen’) where allstandard data types would be a waste of space. Besides reading and writing individual bits one shouldimplement a convenient search for the next set (or cleared) bit.In FXT the class ([FXT: class bitarray in ds/bitarray.h]) is used for example for lists of small primes([FXT: file mod/primes.cc]), in transpositions ([FXT: transpose ba in aux2/transpose ba.h] and [FXT:transpose2 ba in aux2/transpose2 ba.h]) and several operations on permutations. The public methodsare// operations on bit n:ulong test(ulong n) constvoid set(ulong n)void clear(ulong n)void change(ulong n)ulong test_set(ulong n)ulong test_clear(ulong n)ulong test_change(ulong n)// operations on all bits://////////////test whether n-thset n-th bitclear n-th bittoggle n-th bittest whether n-thtest whether n-thtest whether n-thbit setbit is set and set itbit is set and clear itbit is set and toggle itCHAPTER 10.
DATA STRUCTURES222void clear_all()// clear all bitsvoid set_all()// set all bitsint all_set_q() const;// return whether all bits are setint all_clear_q() const; // return whether all bits are clear// scanning the array:// Note: the given index n is included in the searchulong next_set_idx(ulong n) const// return index of next set or value beyond endulong next_clear_idx(ulong n) const // return index of next clear or value beyond endCombined operations like ‘test-and-set-bit’, ‘test-and-clear-bit’, ‘test-and-change-bit’ are often neededin applications that use bit-arrays.
This is underlined by the fact that modern CPUs typically haveinstructions implementing these operations.On the x86 architecture the corresponding CPU instructions asstatic inline ulong asm_bts(ulong *f, ulong i)// Bit Test and Set{ulong ret;asm ( "btsl %2, %1 \n""sbbl %0, %0": "=r" (ret): "m" (*f), "r" (i) );return ret;}(cf. [FXT: file auxbit/bitasm.h]) are used. If no specialized CPU instructions are available macros as#define DIVMOD_TEST(n, d, bm) \ulong d = n / BITS_PER_LONG; \ulong bm = 1UL << (n % BITS_PER_LONG); \ulong t = bm & f_[d];are used, performance is still good with these (the compiler of course replaces the ‘%’ by the correspondingbit-and with BITS_PER_LONG-1 and the ‘/’ by a right shift by log2 (BITS_PER_LONG) bits).The class does not supply overloading of the array-index operator [] because the writing variant wouldcause a performance penalty.One might want to add ‘sparse’-versions of the scan functions for large bit-arrays with only few bits setor unset.10.7Resizable arrayA resizable array is a container utility that, besides the array itself, uses a minimal (constant) amount ofmeta-data.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
