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
Dostları ilə paylaş: |