Algorithms and Data Structures. Lecture 4 – Stack, queue and heap

Август 3, 2022

Главная
Разное
Algorithms and Data Structures. Lecture 4 – Stack, queue and heap

Содержание

2. CONTENT Preface Stack Queue Heap Heap >
3. PREFACE Logical Data Structures Linear (Stack, Queue, etc.) Non-linear (Tree, Hash-Table, Graph, etc.) A Linear data
4. STACK It is a linear data structure that follows the LIFO (Last-In-First-Out) principle Last added item
5. STACK:API boolean empty() – Returns whether the stack is empty – Time Complexity : O(1) int
6. STACK:EXAMPLE Topmost item at position n-1 (Array) Topmost item at position 0 (Linked List)
7. QUEUE It is a linear data structure that follows the FIFO (First-In-First-Out) principle First added item
8. QUEUE:API boolean empty() – Returns whether the queue is empty int size() – Returns the size
9. QUEUE:EXAMPLE It is also possible to provide two methods for each of the followings: Peek peek()
10. HEAP
11. HEAP It allows you to find the *largest/smallest element in the heap in O(1) time Extracting
12. HEAP:INSERTION – O(LOG(N)) A new item is added as the last element Recursive actions (traverse up):
13. HEAP:HEAPIFY – O(LOG(N)) Max Heap example Heapify(i) – fixes the violation of heap property at any
14. HEAP:EXTRACT_MIN – O(LOG(N)) Min Heap example A root item is replaced with the last element Recursive
15. HEAP:METHODS Public: empty() – Returns whether the heap is empty size() – Returns the size of
16. HEAP > There are several comparisons in Heap It is not possible to use >, Comparable
17. HEAP >
18. LITERATURE Algorithms, 4th Edition, by Robert Sedgewick and Kevin Wayne, Addison-Wesley Chapter 1.3, 2.4
20. Скачать презентацию

Слайд 2

CONTENT
Preface
Stack
Queue
Heap
Heap>

Слайд 3

PREFACE
Logical Data Structures
Linear (Stack, Queue, etc.)
Non-linear (Tree, Hash-Table, Graph, etc.)
A Linear

data structure has data elements arranged in a sequential manner and each member element is connected to its previous and next element
Data structures where data elements are attached in hierarchical manner are called non-linear data structures. One element could have several paths to another element
Logical Data Structures are implemented using either an array, a linked list, or a combination of both

Слайд 4

STACK
It is a linear data structure that follows the LIFO (Last-In-First-Out)

principle
Last added item will be served first
It has only one end (named as ‘top’)
Insertion and deletion operations are performed at the top only
A stack can be implemented using linked list as well as an array. However, extra restrictions must be applied in order to follow LIFO

Слайд 5

STACK:API
boolean empty() – Returns whether the stack is empty – Time

Complexity : O(1)
int size() – Returns the size of the stack – Time Complexity : O(1)
T peek() – Returns a reference to the topmost element of the stack – Time Complexity : O(1)
T push(T) – Adds the element at the top of the stack – Time Complexity : O(1)
T pop() – Retrieves and deletes the topmost element of the stack – Time Complexity : O(1)

Слайд 6

STACK:EXAMPLE
Topmost item at position n-1 (Array)
Topmost item at position 0 (Linked

List)

Слайд 7

QUEUE
It is a linear data structure that follows the FIFO (First-In-First-Out)

principle
First added item will be served first
It has two ends (named as ‘Front’ and ‘Back’)
Insertion (enqueue) and deletion (dequeue) operations are performed at different sides
A queue can be implemented using linked list as well as an array. However, it shows better performance with linked list, which has both head and tail references

Слайд 8

QUEUE:API
boolean empty() – Returns whether the queue is empty
int size() –

Returns the size of the queue
T peek() – Returns a reference to the front element of the queue
T enqueue(T) – Adds the element at the end of the queue
T dequeue() – Retrieves and deletes the front element of the queue

Слайд 9

QUEUE:EXAMPLE
It is also possible to provide two methods for each of

the followings:
Peek
peek() – returns null when queue is empty
element() – throws an exception when queue is empty
Enqueue
boolean offer(T) – returns false if it fails to insert
add(T) – throws an exception if it fails to insert
Dequeue
remove() – returns null when queue is empty
poll() – throws an exception when queue is empty

Слайд 10

HEAP

Слайд 11

HEAP
It allows you to find the *largest/smallest element in the heap

in O(1) time
Extracting the *largest/smallest element from the heap (i.e. finding and removing it) takes O(log n) time
Heap can be implemented using:
Array (manipulating its indices)
Nodes with references to their right and left children (not covered)
The root is stored at index 1, and if a node is at index i, then
Its left child has index 2i
Its right child has index 2i+ 1
Its parent has index i/2

*largest/smallest – largest for Max Heap and smallest for Min Heap

Слайд 12

HEAP:INSERTION – O(LOG(N))
A new item is added as the last element
Recursive

actions (traverse up):
Compare with parent
Exchange if it violates the property
Stops when no other violations or it has reached the root

Слайд 13

HEAP:HEAPIFY – O(LOG(N))
Max Heap example
Heapify(i) – fixes the violation of heap

property at any position i (assuming that violation is only at i`th position)
Replace an element at i with the largest of children
Recall Heapify(largestIndex)
Stops when current item is larger than children (or equal) or there`s no other child items

Слайд 14

HEAP:EXTRACT_MIN – O(LOG(N))
Min Heap example
A root item is replaced with the

last element
Recursive actions:
Heapify(rootIndex)

Слайд 15

HEAP:METHODS
Public:
empty() – Returns whether the heap is empty
size() – Returns the

size of the heap
T getMax() or getMin() – Returns a reference to the root element of the heap
T extractMax() or extractMin() – Retrieves and deletes the root element of the heap
insert(T) – Adds the element to the heap
Private:
heapify(index) – can perform heapify actions starting from position ‘index’
traverseUp(index) – can perform traverseUp actions starting from position ‘index’
leftChildOf(index) – returns the index of the left child item
rightChildOf(index) – returns the index of the right child item
parentOf(index) - returns the index of the parent item
swap(index1, index2) – exchanges two elements by their positions

Слайд 16

HEAP>
There are several comparisons in Heap
It is not possible

to use >, <, <=, etc. operators when dealing with objects (not primitives)
Comparable is an interface that provides a method obj1.compareTo(obj2), which returns a number
More than 0 when obj1 is greater than obj2
Less than 0 when obj1 is smaller than obj2
Exactly 0 when obj1 is equal to obj2
That comparison is defined in object itself
Classes that are already Comparable: Integer, Double, String, etc.
If heap stores objects of user-defined type, then that type should implement Comparable interface

Слайд 17