lOMoARcPSD|44644628

Module 5 DSA Notes

DSA (Visvesvaraya Technological University)

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university

Downloaded by Prince Allu (alluprince69@[Link])
 lOMoARcPSD|44644628

Data Structures and Applications [BCS304]-3 Sem A Section Sankhya N Nayak

-------------------------------------------------------------------------------------------------------------------------------------

MODULE 5:

PRIORITY QUEUES
A priority queue is a type of queue that arranges elements based on their priority values. Elements
with higher priority values are typically retrieved before elements with lower priority values.
A priority queue is an extension of a queue that contains the following characteristics:
• Every element in a priority queue has a priority value associated with it
• The element with the higher priority will be moved to the top and removed first
• If two elements in a priority queue have the same priority value, they’ll be arranged using
the FIFO principle

variants
1. Single Ended
2. Double ended

1. Single Ended priority Queues

There are two types of single ended priority queues based on the priority of elements.
• If the element with the smallest value • If the element with a higher value has
has the highest priority, then that the highest priority, then that priority
priority queue is called the min priority queue is known as the max priority
queue. queue.

The operations supported by min priority The operations supported by min priority
queue are queue are
SP1: (peek)Return element with minimum priority SP1: (peek)Return element with maximum priority
Sp2:Insert element with an arbitrary priority Sp2:Insert element with an arbitrary priority
Sp3:delete element with minimum priority Sp3:delete element with maximum priority

Dept. of CSE, JNNCE, Shivamogga

1 / 22
Downloaded by Prince Allu (alluprince69@[Link])
 lOMoARcPSD|44644628

Data Structures and Applications [BCS304]-3 Sem A Section Sankhya N Nayak

-------------------------------------------------------------------------------------------------------------------------------------

Priority queue can be implemented using an array, a linked list, a heap data structure, or a binary
search tree. Among these data structures, heap data structure provides an efficient implementation
of priority queues.

2. Double Ended priority Queues DEPQ)[

A double-ended priority queue (DEPQ) is a data structure similar to a priority queue, but allows for
efficient removal of both the maximum and minimum, according to some ordering on the keys (items)
stored in the structure. It is a min and max priority queue rolled into a single structure.
The operations supported by double ended priority queue are
DP1: Return element with minimum priority
DP2: Return element with maximum priority
DP3: Insert element with an arbitrary priority
DP4: delete element with minimum priority
DP5: delete element with maximum priority

Applications
1. To implement network buffer : Keep waiting packets in buffer. When link is available transmit
packet with highest priority (Delete max). Adding packet to buffer is done with Insert
operation. If buffer is full and packets have to be dropped delete one with min priority(delete
min).
2. External Quick Sort : In an external sort, we have more elements than can be held in the
memory of our computer. The elements to be sorted are initially on a disk and the sorted
sequence is to be left on the disk. When the internal quick sort method outlined above is
extended to an external quick sort, the middle group M is made as large as possible through
the use of a DEPQ. The external quick sort strategy is:
A. Read in as many elements as will fit into an internal DEPQ. The elements in the DEPQ will
eventually be the middle group of elements.
B. Read in the remaining elements. If the next element is <= the smallest element in the
DEPQ, output this next element as part of the left group. If the next element is >= the
largest element in the DEPQ, output this next element as part of the right group.
Otherwise, remove either the max or min element from the DEPQ (the choice may be
made randomly or alternately); if the max element is removed, output it as part of the
right group; otherwise, output the removed element as part of the left group; insert the
newly input element into the DEPQ.
C. Output the elements in the DEPQ, in sorted order, as the middle group.
D. Sort the left and right groups recursively.

Dept. of CSE, JNNCE, Shivamogga

2 / 22
Downloaded by Prince Allu (alluprince69@[Link])
 lOMoARcPSD|44644628

Data Structures and Applications [BCS304]-3 Sem A Section Sankhya N Nayak

-------------------------------------------------------------------------------------------------------------------------------------

OPTIMAL BINARY SEARCH TREES

A binary search tree is one of the most important data structures in computer science. One of its
principal applications is to implement a dictionary, a set of elements with the operations of searching,
insertion, and deletion.

If probabilities of searching for elements of a set are known e.g., from accumulated data about past
searches it is natural to pose a question about an optimal binary search tree for which the average
number of comparisons in a search is the smallest possible.

In many applications the cost of searching is very important. So, it is required that the overall cost of
searching should be as less as possible. And we know that search time of BST is more than
the Balanced Binary Search Tree, as Balanced Binary Search tree has less number of levels than the
BST. And there is one way which can further reduce the cost than the Balanced BST, which is Optimal
Binary Search Tree . Let us understand that by following example.

As there are 3 different keys, so we can have total 5 various BST by changing order of keys. The total
number of binary search trees with n keys is equal to

So following are the various possible Binary Search Trees of the above data. And also the overall cost
for searching for each BST. The cost is computed by multiplying each node’s frequency with the level
of tree( Here we are assuming that the tree starts from level 1 ) and then add them to compute the
overall cost of BST.

As it is shown in above figure that 2nd BST is balanced and the 4th BST is not balanced, though it’s
cost is less than the cost of Balanced BST and its cost is the least among all, so it is our Optimal Binary
Search Tree for the given data.

Dept. of CSE, JNNCE, Shivamogga

3 / 22
Downloaded by Prince Allu (alluprince69@[Link])
 lOMoARcPSD|44644628

Data Structures and Applications [BCS304]-3 Sem A Section Sankhya N Nayak

-------------------------------------------------------------------------------------------------------------------------------------

As a general algorithm, this exhaustive-search approach is unrealistic as n increases: Therefore dynamic

programming approach, we will find values of C(i, j) for all smaller instances of the problem, although
we are interested just in C( 1, n).

To derive a recurrence underlying a dynamic programming algorithm, we will consider all possible
ways to choose a root ak among the keys ai, . . . , aj . For such a binary search tree , the root contains
key ak, the left subtree Tik−1 contains keys ai, . . . , ak−1 optimally arranged, and the right subtree
Tjk+1contain s keys ak+1, . . . , aj also optimally arranged.

If we count tree levels starting with 1 to make the comparison numbers equal the keys’ levels, the
following recurrence relation is obtained:

General formula for calculating the minimum cost is:

C[i,j] = min{c[i, k-1] + c[k,j]} + w(i,j). if i<j
i<k<=j
= Pi if i=j
= 0 i>j

The algorithm computes C(1, n)—the average number of comparisons for successful searches in the
optimal binary tree.

Dept. of CSE, JNNCE, Shivamogga

4 / 22
Downloaded by Prince Allu (alluprince69@[Link])
 Downloaded by Prince Allu (alluprince69@[Link])
5 / 22
2. 2o4
Cot32
-i=1
ete Woy
C3,3] c 2.08=
C2,2 C 2|4
25Co= j-i:3
clo,oJ l4 -
Nate
224=3
19 Co2 -2-i
C24-B |312
2
12 Wo2
234-4 Coi
3 3
WB4
(
=0. 4 4 Cu
o C22
2 Woo
3 2
ustng weighfs all Shop
Roo
Cuy Coo
stepl:
Sol:
atchnsuccasnfel 9:
3 Keys
succeufol P: 10
25 20
Search
at a2 al
give ie foR
fhe
Optimal tnd Exarnple
data: BST
lOMoARcPSD|44644628
 Downloaded by Prince Allu (alluprince69@[Link])
6 / 22
Root 3)9 Ot
C[2,8
+
[3,43= c
Root
|2,
C3,
8] e,
+ 2)
w,3]
+
4 = 12 T
+ J o, c Co,2I c
=
Step
2
3
Ca3
3 =23 W23=3
2 ho2
& Wo Co
3I=I+(+
2 =+3
2+3
lOMoARcPSD|44644628
 lOMoARcPSD|44644628

Step 4' j-i= .

qs,3] = c[o, o] +

(c o, 21 + ef2,2)J
Rsot
25
3

Rot.

T t 3

step

9 + 3

7 / 22
Downloaded by Prince Allu (alluprince69@[Link])
 lOMoARcPSD|44644628

Constuchon ef Dptimal
&ST Fooo table
Root is Ros 2n
2nd key 15

Roy 16

Ro
(20 ) 3.

8 / 22
Downloaded by Prince Allu (alluprince69@[Link])
 lOMoARcPSD|44644628

O
Hashena'
ehasacls
Hasina the
dr ansematon irg
nto uusually sA«e fdd lenyil vale i hay

Repacsent t ginal sshn tems in

edex , seaach, dala
Hashinj andKe most
dictionay idatabase 9t s asla

ceni technsqws do t ne ekhan comfpaie

OC) me
toeee oCm) and balancal ainay
e anck
ACaich
oC log ) Ume.
e bmains Samaa
Data bucket addras
statc

Hashing Dynamc Buckets ase addad and Temoved

on demand

4 siaiic Hashina
e haini
Hash tables
Hashin3 Oveflow
unelWo ns Honding Ppe Addresir
Diuigion lineas
paobing
mid Lquarl quadaaie
psobi
Foldng
L Sue alng Aehas hing
Aandom
LfolAing at the boundausProaig
Digit analyss
2. Dyamic Hashing
Coovexiina Kays tv
itegeas

using olinctki e isacttless dineas) Dymam

Hasking
9 / 22
Downloaded by Prince Allu (alluprince69@[Link])
 lOMoARcPSD|44644628

statc Hashing n state haskigkaales

sicd in a table , ht
konaypais a
into uckets
Colla tA Aash table , paat:Tonnd

ETo3,htT3. At To-1.
stot o elt Hash table eit
0acos atan
buckets an d
2
2 chaa Cer 2slots Pea buc kol

25 eacon

Kay density Cno o Pa ink table)

Ctotal no aposble kes

oloadog desus = S=st

kooding faclk sb b bucket si ze

Suppose b 26 S 2 and n- io no. f wosels

1 ieionan)
doading ac 226

Hashing funclons A hash uncken aps a

ka
Joucket in the hash talle
ento a

K- L L loeatton

Cateria in salecing hash nchins

L skould be easy and auick to Compul

as as as posseble, H should disti bute

addesses wriformy aueid eustkuina and

co lision.
10 / 22
Downloaded by Prince Allu (alluprince69@[Link])
 lOMoARcPSD|44644628

Hashin anato Coninuad

uision mekod EX D =97

H C320S-4 47148) =67.
idaly
assues
galaie itegees

k . D

to D- ase generated
enerrte

Buckat addsss es o

t mi nedi22
Sually D is chosen axafly
o. stRout small dwisks)
colli sios. Cptir
emed- Squae method.
Home bucket a ka
Da onined by squorsig k
kat
bits
a Paaopiat.
mumber
o
and -then asing
h Sqase
fom Ra middle o
to 21 ao2s
Ex: k 3205
Keg CE) ,
ha
onust be used fer all kos. n
Sasne postns
tuaed
above example 4 35" lais eon ight aae

Fol ding metRod

all oue
inp Several pask ,

k is paioned
Ke same
lenaR. Kan
lengk. Ren
last being
peseb to obtain hash oddlaass k.
Rese as
aldel tvget

shiftoldseg' 2 digit pat:hon

32+ OS
HC32 os)
HC7148) =1 +48
ore kale must be
Sosme
ex 2 K=12 3 20324I1220 .(3 digt paslano
23+ 203 + 241 + 112+20 =
6 9.
C leoust significamt dgs ase
inad)
11 / 22
Downloaded by Prince Allu (alluprince69@[Link])
 lOMoARcPSD|44644628

laad at patHon
Foling
tolding oct boundauas: Ka is
S

boundarias before ading

Ex 2323 2 4 2ao
RaveR
302 211

302+24+2 +20 892

23 E
es eke
eher
n oS stotie
statie les
D)iait Amaysis s ed case

in
n
advance
advanca
knowon
known
ne table
table as

all ha
te kays
kaqs a Decima, Hexa
Todx
is iiea p3ated uaina
Each Ka distsi buon
keoed
Tha digits ase
examlned an s

eoraiiks
oher Tnbeas) keapi7
Ctails lomge addsess nte Tage
to gves auddaes
Smal enough
digits
Re hask table .

Ce Conveating_ Kays do imteg ens

hen
kas
Can be conv eatal -to it eg e befeea fendnj
iegss th
buckat Jocalidm tkem
Onignel Int sivingo Int Cehas k EI)
1int 0, i d
oRilCka Cil = '\e)

Each chonacta ts Convealal unlo uniaue i egeas and

S SuTme eHega etunmd ba fneton is
ot much Conge Ron 8bits
A vasialion Co l be tingKa
12 / 22
Downloaded by Prince Allu (alluprince69@[Link])
llotsing at (* in
in
 lOMoARcPSD|44644628

tka awe examp le

n + CCint) ka Ci <<8',
sL efte Su onuslg

Ovealow Handling
thoat
Suppose hen olocolzon we
a ke
ke, and

memoy locako is alscady occupied , ut Reslts in

Collison
CA Open Addaassing-:
A) aaslue eollision , n thes
mekod e y end maxt
asailable locostien
acceRding to eaiteLa

ext available locoticn

naa Psoaing Seasck f
TCh+] . .. eanlil an
Linearys TCh, TCh+],
enp docolioh ound.

EX Suppese bucka size = , &

letsing hask addbesses
odbasses
ehoanackas
Recosd: A B C D Y 2

HCk 4 2

Suppose Ran endearsl indo fable

INDEX. 4
3 S
TABLE
D .

1
eColksion Y Coliin xcolk
CoRsn
13 / 22
Downloaded by Prince Allu (alluprince69@[Link])
 lOMoARcPSD|44644628

Secach. Ctid eack

Pveage no
Probes for Successfl ecdsd1)

A B C D 22
+ + 2 +2 +2+3

asch
n o probes
ATSuCca4s
al se

4+ 3+ 2+I + 2+I1+8
O 7+ 6+5 + 3- 6

to phy locon eack of

.
o probes ind an

lo c ateons
tend to euste Cappeos
cusHea Cappeos
aReords

isadesantoge a ex tto
anohor)

Racord
incaeageg Seaa ch tma fR
olireas poobirg b
Can
mekods
tagolCorseng
do mini mie
clusleaig

sed Ra localiën
ocalibu
Re
Snsteod of Seaacding
&nodratic proking: localzon
eack ha enpdy
A, h+,
h+2 ete na asy
e addresa h
4+k, h+9, h+l6.
h, A+i,

hash unclo is
Second
Rehashing CDouble Hashing)
usd aesolve colli_ion.
*C)= h tRa
hask unclon
Siuppase st
HCR)= A [Link]
Second O
can be seaschel at
locathons
emp
A, Ah', A+2h, A+sk
Kandom Paobing: Arandom localion is ound teaa,
14 / 22 and ud to Aeaelve
a psedo Tandom qenerataL
Downloaded by Prince Allu (alluprince69@[Link]) colisim
 lOMoARcPSD|44644628

s ad vastage o ppen addsessi

saakee kagg Sa 'o'.
A, , e, D
ex Cosn si der
A
csion

Tecos&
Stappos e dalet
Seaadh o C. whom ou
Lart
NoO locoon
at ke . At 'o
Aas ou
at A Da
2
A is Resa, Next you seasck
NULL So it Tehurns a nett presert
D So
ase taken to
Some ofhea raasie3

ness
handle +Kis

A ust is naintaimad
ased
Moreaaue Hy
.

C choining
e each ka

L- acos ati||atoe
NOLL

Ex 2 A D

15 / 22
Downloaded by Prince Allu (alluprince69@[Link])
 lOMoARcPSD|44644628

isod vantage cells f tha da

chaining 3 emwsy

ul s

mi Hash4: ensue
Jo good P oT 7manCe
,
2
a
ohenuwe
has h table
LeRs8aly lo wn cazase dAa Si2e of a

Cessa taushakd.
oo adinga denay excaads a Psuspe cifed
al ading
has meheds
Y cderstandehg 2
popacla d 1amie

another alaneog less Nat us

ne AseR dincth andd ,

CSe &e gollohoing hash uncksz

ACk
AO A

A oo A

CI O OO
2

Jha
Disectois
Dynaic Hashung Osing hCE)
TLnbe ef
biHfs af
diiectdy 'ddepends on -Re indxig
is done

ha dewcty. han
c2&.ed fo in dex
is 24.
2 bits size eduiecty Cnph-2)

oo A0, B3o last 2

C2, C2
deteovre nal
4IBI|
Al, B
thaia backet addsass
2 10
last 2 bits
wanto to add CS _lo
Stppose -
can net addit AIga
11o o but we

bucket S &it is
al eady occapied
kecausse Re Epio= 2, e

bg Al B 16 / 22
Downloaded by Prince Allu (alluprince69@[Link])
 lOMoARcPSD|44644628

So We no. bits to 3'

Ao,Bo deph 3
Al,81 nexE hase h
so
e
a
O C

o >es C Lil hash to [Link]

LO albrad have AH and
oo we

.'. dopth ill be inereaad

Nole Lmply lcalion back S point td ecoa

Comon ast 2 its

Ao, eo
*, BIs moved
ALCI| bseve
to too Ceda feR

6
s
tooot and las

Otlo
es e 4its loO| as

Compaand do el

c s sBooed in

to Second bucket

a Asra Doubing
ATTOH fs hea, u
sed
Io Oveao. Howev aahashina is done
on n etries hera buckats ovefos

No drasing baekoard inks

ehasacteas (a-e) aae use d s mesS
Ould point t 17 / 22
ho whe he
Downloaded by Prince Allu (alluprince69@[Link])
 lOMoARcPSD|44644628

(to)
isectiyless Dmamic Hashina C&inaan Dymanic Haskg)
n eaalea
Snsiead of daeoty o bucket poinles taaed

nethod, n aa buckets is sd
sed Lo Kanp toack ef
Two vaRiables and
tRe actie buc kefs
is h stat o a ehain of buckels
Each actuue bucke
uoi ll be actuwe.
buckels O -

2+-\
At omy
a om chain ae calad oveaoto
buckeis
The Telain mug
buckels
ex t asit A = 2 and

B4Ad A BS C2
lo

Insett too
6o0 Olo

() p A Bss C -

c3 - e4
e ache loucka

alseody occpeo loy

occpel oy
Tesults in ol an t is

Henca ovelloo
Al and 8S in
a Ca ona
kat
Ovaoo is e handlA by aivalg
extra [Link]) Tucket 4ooD is actvat eA
achashal unga +1)= 3 bits. ? B
otKess ase
ooo bucke to loo bucke. cs
Rom
S adddas do ovesClow bucket
O0 ol
ca- (4 |Bs CS
Ce A-A AC e2 -

new acwe
18 / 22
nseat C Downloaded by Prince Allu (alluprince69@[Link])
 lOMoARcPSD|44644628

Now he we fu tD add
inSetb)
ehick is alseadocupas
geis
we have es.
buckek
by Al BS and
ond in ov ea(low
). Rehash
So
So acva one 3eRe buckot lo
amdes sell
koeth coligiom BS
oucketfs
and Al & C o
ove to ne acbe buckds
occupy bucket ool Seed in
occP1

19 / 22
Downloaded by Prince Allu (alluprince69@[Link])
 lOMoARcPSD|44644628

Kellist Jaees

definud seng dle concpt

extomded binag skee all empy binay
dables have been seplaced by sauoe node.

nodes extes al nodes

Jhee 2 vasietis lefst rs
Oweight based CwBLT)
O Height base C#eLT)
based kallist Taeas CHBLT)

sightokld(x), ke shorlet Cx) is

Su ght ehildaon - extenl
lengtt shoteet patt fem
extenall oe

&hetast(AigktchildC«)8SoRak
2
Ex: A
2

20 / 22
Downloaded by Prince Allu (alluprince69@[Link])
 lOMoARcPSD|44644628

A agtet ee hen nt enpty should salisy

d)s hatast (aightehldC)
shatest Cat ahd
inlial mode

Fig C^) nat lalist

skalastlasclalda)
shlas (aft ektd Ce))is met 1.

stanchue
s saet ypeda shud daplesl leltstTea
daftistTaee datehl,
3 elenet' elenent data
Teee Righteild
nt sheto
shelerl

Mi TAee
nodles TageuCmalle) han
shiel key
ehilde.
key 2
2

x:

2
12

dallist trea
Eranple

21 / 22
Downloaded by Prince Allu (alluprince69@[Link])
 lOMoARcPSD|44644628

Weit basel kopls saas.

det be meonbe cenlesnal oodes

is extenal
iteenl
Ciot 4)+
Clepeekil ot (aglt chil))

Ex
2

Fig A
lze
Loeight biased laflasl
A
inlmal oda the value lat lild
at
chi ld
S value Bi ght
A
al c Cefe)

Fi8
X

22 / 22
Downloaded by Prince Allu (alluprince69@[Link])