Extracting the node with minimum key

BINOMIAL-HEAP-EXTRACT-MIN(H)1 find the root x with the minimum key in the root list of H,       and remove x from the root list of H 2 H ′ ← MAKE-BINOMIAL-HEAP()3 reverse the order of the linked list of x 's children,       and set head [ H ′] to point to the head of the resulting list4 H ← BINOMIAL-HEAP-UNION(H, H ′)5 return x

 

 

 

Рис. 5

 

Decreasing a key

BINOMIAL-HEAP-DECREASE-KEY(H, x, k) 1 if k > key [ x ] 2 then error "new key is greater than current key" 3 key [ x ] ← k 4 y ← x 5 z ← p [ y ] 6 while z ≠ NIL and key [ y ] < key [ z ] 7 do exchange key [ y ] ↔ key [ z ] 8   ▸ If y and z have satellite fields, exchange them, too. 9   y ← z 10   z ← p [ y ]

 

Рис. 6

 

Deleting a key

BINOMIAL-HEAP-DELETE(H, x)1 BINOMIAL-HEAP-DECREASE-KEY(H, x, -∞)2 BINOMIAL-HEAP-EXTRACT-MIN(H)

 

 

Fibonacci Heaps

 

Structure of Fibonacci heaps

 

Pic. 1

Inserting a node

FIB-HEAP-INSERT(H, x) 1 degree [ x ] ← 0 2 p [ x ] ← NIL 3 child [ x ] ← NIL 4 left [ x ] ← x 5 right [ x ] ← x 6 mark [ x ] ← FALSE 7 concatenate the root list containing x with root list H 8 if min [ H ] = NIL or key [ x ] < key [ min [ H ]] 9 then min [ H ] ← x 10 n [ H ] ← n [ H ] + 1

 

 

Pic. 2

 

Uniting two Fibonacci heaps

FIB-HEAP-UNION(H ₁, H ₂)1 H ← MAKE-FIB-HEAP()2 min [ H ] ← min [ H ₁]3 concatenate the root list of H ₂ with the root list of H 4 if (min [ H ₁] = NIL) or (min [ H ₂] ≠ NIL and min [ H ₂] < min [ H ₁])5 then min [ H ] ← min [ H ₂]6 n [ H ] ← n [ H ₁] + n [ H ₂]7 free the objects H ₁ and H ₂8 return H

 

Extracting the minimum node

FIB-HEAP-EXTRACT-MIN(H) 1 z ← min [ H ] 2 if z ≠ NIL 3 then for each child x of z 4         do add x to the root list of H 5             p [ x ] ← NIL 6     remove z from the root list of H 7     if z = right [ z ] 8        then min [ H ] ← NIL 9        else min [ H ] ← right [ z ]10             CONSOLIDATE(H)11     n [ H ] ← n [ H ] - 112 return z

 

 

Pic. 3

CONSOLIDATE(H) 1 for i ← 0 to D (n [ H ]) 2 do A [ i ] ← NIL 3 for each node w in the root list of H 4 do x ← w 5    d ← degree [ x ] 6    while A [ d ] ≠ NIL 7        do y ← A [ d ] ▹ Another node with the same degree as x. 8            if key [ x ] > key [ y ] 9              then exchange x ↔ y 10           FIB-HEAP-LINK(H, y, x)11           A [ d ] ← NIL12           d ← d + 113    A [ d ] ← x 14 min [ H ] ← NIL15 for i ← 0 to D (n [ H ])16 do if A [ i ] ≠ NIL17          then add A [ i ] to the root list of H 18            if min [ H ] = NIL or key [ A [ i ]] < key [ min [ H ]]19               then min [ H ] ← A [ i ]FIB-HEAP-LINK(H, y, x)1 remove y from the root list of H 2 make y a child of x, incrementing degree [ x ]3 mark [ y ] ← FALSE

 

Структуры данных для непересекающихся множеств

 

Make_ Set(x) x - представитель

Union (х, у)

Find_Set(x)

a

b

c

d

e

f

g

a

b

c

d

e

f

g

a

b

c

d

e

f

g

a

b

c

d

e

f

g

a

b

c

d

e

f

g

Весовая эвристика – короткий список присоединяем к длинному

Pic. 3

Первая эвристика - объединение по рангу (высота)

Вторая эвристика - сжатие пути при выполнении Find_Set

Pic. 1

Pic. 2

Find_Set(x) – O(1)

Union(х, у) – O(n)

 

 

Хеш-таблицы

 

 

1

3

Колизии

Index = key%m – hash функция

Разрешение коллизий в самом массиве

1

11

3

31

Удаление 11

1

-1

3

31

1

12

3

31

Удаление 2

1

1

31

3

Двойное хеширование

h (k, i) = (h₁ (k) + i*(1+h₂ (k))) mod m,

Построение хеш-функции методом умножения

к

A

1

kA

Pic. 1

H(k) =kA&0xffff

m = 2^p ; p=16;

 

Универсальное хеширование

h_a,b(k)=((ak+b) mod p) mod m; 1<a<p; 0<b<p; p>max(k)

 

Пространственноехеширование

 

Pic. 2

(28 bits)

Y (2 bits)

X (2 bits)

 

 

 

 

 

 

Y (16 bits)

X (16 bits)

 

Pic. 3

 

CRC алгоритм

10011011

 +11001010

--------

01010001

 10011011

-1 1001010

--------

 01010001

10000: 10101

10101 1

0101

110000: 10101

10101 11

11010

10101

1111

100000: 10101

10101  10

01010

00000

1010

100000: 0101

0101 10

01010

1010

1010000: 0101

01010

0101

11110

0101

1011

 

Pic. 4

 

Pic. 5

 

Pic. 6

r=*p++;

while (len--)

{

       t = r;

       r = *p++;

       r^=table[t];

}

 

Поиск подстроки

Рис 1

The naive string-matching algorithm NAIVE-STRING-MATCHER(T, P)1 n ← length [ T ]2 m ← length [ P ]3 for s ← 0 to n - m 4 do if P [1 ‥ m ] = T [ s + 1 ‥ s + m ]5      then print "Pattern occurs with shift" s

Рис 2

 

Procedure NAIVE-STRING-MATCHER takes time O ((n - m + 1) m)

The Rabin-Karp algorithm

 

Пусть Σ = {0, 1, 2,..., 9}

p = P [ m ] + 10 (P [ m - 1] + 10(P [ m - 2] + · · · + 10(P [2] + 10 P [1]))).

t ₀ <= T [1 ‥ m ] in time Θ(m)

m=5

10(31415 - 10000 · 3) + 2 = 14152.

=> сложность O(n)

h=d^(m-1)

q – простое число

dq<maxint

Рис 3

RABIN-KARP-MATCHER(T, P, d, q) 1 n ← length [ T ] 2 m ← length [ P ] 3 h ← d^{m -1} mod q 4 p ← 0 5 t ₀ ← 0 6 for i ← 1 to m       ▹ Preprocessing. 7 do p ← (dp + P [ i ]) mod q 8   t ₀ ← (dt ₀ + T [ i ]) mod q 9 for s ← 0 to n - m   ▹ Matching.10 do if p = t_s 11      then if P [1 ‥ m ] = T [ s + 1 ‥ s + m ]12              then print "Pattern occurs with shift" s 13   if s < n - m 14      then t_{s +1} ← (d (t_s - T [ s + 1] h) + T [ s + m + 1]) mod q

=> сложность O(n) в среднем и O(n*m) в худшем случае.