Cs520 Advanced Analysis of Algorithms and Complexity



Yüklə 198 Kb.
səhifə3/3
tarix17.09.2023
ölçüsü198 Kb.
#144546
1   2   3
CH02- ADT and its specification

Queue

Priority Queue

  • A priority queue is a structure with some aspects of FIFO queue but
    • in which element order is related to each element’s priority,
    • rather than its chronological arrival time.
  • As each element is inserted into a priority queue, conceptually it is inserted in order of its priority
  • The one element that can be inspected and removed is the most important element currently in the priority queue.

Union-Find ADT for Disjoint Sets

  • Through a Union operation, two (disjoint) sets can be combined.
    • (to insure the disjoint property of all existing sets, the original two sets are removed and the new set is added)
    • Let the set id of the original two set be, s and t, s != t
    • Then, new set has one unique set id that is either s or t.
  • Through a Find operation, the current set id of an element can be retrieved.
  • Often elements are integers and
    • the set id is some particular element in the set, called the leader,

Union-Find ADT e.g.

  • UnionFind create(int n)
    • // create a set (called sets) of n singleton disjoint sets {{1},{2},{3},…,{n}}
  • int find(UnionFind sets, e)
    • // return the set id for e
  • void makeSet(unionFind sets, int e)
  • void union(UnionFind sets, int s, int t)
    • // s and t are set ids, s != t
    • // a new set is created by union of set [s] and set [t]
    • // the new set id is either s or t, in some case min(s, t)

Dictionary ADT

  • A dictionary is a general associative storage structure.
  • Items in a dictionary
    • have an identifier, and
    • associated information that needs to be stored and retrieved.
    • no order implied for identifiers in a dictionary ADT

Video Lecture of the topic can be found at

  • Video Lecture of the topic can be found at
  • Computer Algorithms - Abstract Data Types (ADT)
  • https://youtu.be/aHWNxF0c08U
  •  
  • Basics for Analysing Computer Algorithms
  • https://youtu.be/n1ArVTvMJtE

Yüklə 198 Kb.

Dostları ilə paylaş:
1   2   3




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin