• Data Structure, Memory and Pointers

• Operation of sets
• Search (S, k)
• Insert (S, x)
• Delete (S, x)
• Minimum (S)
• Maximum (S)
• Successor (S, x)
• Predecessor (S, x)

126
• Data Structure, Memory and Pointers
• Linked list
• A linked list is a data structure in which the objects are arranged in a
linear order
• Unlike an array, though, in which the linear order is determined by the
array indices, the order in a linked list is determined by a pointer in each
object

• Linked lists provide a simple, flexible representation for sets,

supporting all the operations listed

127
• Data Structure, Memory and Pointers
• Linked list

• As illustrated, each element of a linked list L is an object with a key field

and two other pointer fields: next and prev
• Given an element x in the list, next[x] points to its successor in the linked
list, and prev[x] points to its predecessor
• If prev[x] =NULL, the element x has no predecessor and is therefore the
first element, or head, of the list.
• If next[x] =NULL, the element x has no successor and is therefore the last
element, or tail, of the list

128
• Data Structure, Memory and Pointers
• Searching a linked list LIST-SEARCH(L,k)
x  head[L]
while x  NULL and key[L]  k
do x  next[x]
return x

The procedure LIST-SEARCH(L,k) finds the first element with key k in

list L by a simple linear search, returning a pointer to this element
• If no object with key k appears in the list, then NULL is returned
• For the linked list here, the call LIST-SEARCH (L,4) returns a pointer to
the third element, and the call LIST-SEARCH(L,7) returns NULL

129
• Data Structure, Memory and Pointers
• Inserting into a linked list LIST-INSERT(L,x)
next[x]  head[L]
if head[L]  NULL
then prev[head[L]]  x
head[L]  x
prev[x]  NULL

• Given an element x whose key field has already been set, the LIST-
INSERT procedure “splices” x onto the front of the linked list, as shown
below

130
• Data Structure, Memory and Pointers
• Deleting into a linked list LIST-INSERT(L,x)
if prev[x]  NULL
then next[prev[x]]  next[x]
else head[L]  next[x]
if next[x]  NULL
then prev[next[x]]  prev[x]

• The procedure LIST-DELETE removes an element x from a linked list L

• It must be given a pointer to x, and it then “splices” x out of the list by

updating pointers.
• Before deleting an element, it must first call LIST-SEARCH to retrieve a
pointer to the element

131
• Implementing pointers and objects
• Multiple-array representation of objects
• The figure below represents a collection of objects that have the same
fields by using an array for each field
• Linked list with three arrays

• The array key holds the values of the keys currently in the dynamic set,
and the pointers are stored in the arrays next and prev
• For a given array index x, key[x], next[x], and prev[x] represent an object
in the linked list
•Under this interpretation, a pointer x is simply a common index into the
key, next, and prev arrays.

132
Stack & Queue

133
• Data Structure, Memory and Pointers
• Stacks
• The INSERT operation on a stack is often called PUSH, and the DELETE
operation is called POP
• In a stack, the element deleted from the set is the one most recently inserted:
the stack implements a last-in, first-out, or LIFO.
• The fig. below implements a stack of at most n elements with an array S[1..n]

• The array has an attribute top[S] that indexes the most recently inserted
element
• The stack consists of elements S[1.. top[S]], where S[1] is the element at the
bottom of the stack and S[top[S] is the element at the top
•. When top[S] = 0, the stack contains no elements and is empty
134
• Data Structure, Memory and Pointers
• Stacks (LIFO)
PUSH(S,x) POP(S)
top[S]  top[S] + 1 if STACK EMPTY(S)
S[top[S]]  x then error
else top[S]  top[S] - 1
return S[top[S] +1]

135
Queues (FIFO)
• The INSERT operation on a queue is called ENQUEUE, and we call the
DELETE operation DEQUEUE
• The queue has a head and a tail. When an element is enqueued, it takes its
place at the tail of the queue
• The element dequeued is always the one at the head of the queue
• In a queue , the element deleted is always the one that has been in the set for
the longest time: the queue implements a first-in, first-out, or FIFO.
• The figure below shows one way to implement a queue of at most n-1
elements using an array Q[1..n]

• The queue has an attribute head[Q] that indexes, or points to, its head.
• The attribute tail[Q] indexes the next location at which a newly arriving
element will be inserted into the queue
136
• Data Structure, Memory and Pointers
• Queues

ENQUEUE(Q, x)
Q[tail[Q]]  x
if tail[Q] = length[Q]
then tail[Q]  1
else tail[Q]  tail[Q] + 1

DEQUEUE(Q, x)
x  Q[head[Q]]
if head[Q] = length[Q]
then head[Q]  1
else head[Q]  head[Q] + 1
return x

137
Stack Overflow, Stack Underflow
A stack can also be implemented to have a
maximum capacity. If the stack is full and does not
contain enough slots to accept new entities, it is said
to be an overflow – hence the phrase “stack
overflow”. Likewise, if a pop operation is attempted
on an empty stack then a “stack underflow” occurs.

Push - it specifies adding an element to the Stack. If

we try to insert an element when the Stack is full,
then it is said to be Stack Overflow condition
Pop - it specifies removing an element from the
Stack. Elements are always removed from top of
Stack. If we try to perform pop operation on an
empty Stack, then it is said to be Stack Underflow
condition.
138
Queue Overflow, Queue Underflow

• Queue overflow happens by trying to add a key to a full

queue.
• Queue underflow happens when trying to remove an element
from an empty queue

Summery
Stack and Queue can be implemented using both, arrays and linked
list. The limitation in case of array is that we need to define the
size at the beginning of the implementation. This makes the Stack
or Queue static. It can also result in "Stack or Queue overflow" if
we try to add a key after the array is full. The alleviate to this
problem is, we use dynamic memory allocation of Stack and
Queue.
139
Heap sort
• O (n lg n) worst case—like merge sort.
• Sorts in place—like insertion sort.
• Combines the best of both algorithms.

Heap sort algorithm

Step 1: Build Heap
Step 2: MAX or MIN HEAPIFY
Step 3: Sorting

140
Heap data structure
• Heap A is a nearly complete binary tree.
• Height of node = # of connections on a longest path from the node
down to a leaf.
• Height of heap = height of root = (lg n ).
• A heap can be stored as an array A.
• Root of tree is A[1].
• Parent of A[i ] =A[i /2].
• Left child of A[i ] =A[2i ].
• Right child of A[i ] =A[2i +1].

141
• Maintaining the heap property
• Heap property
• For max-heaps (largest element at root), max-heap property: for all nodes
i, excluding the root, A[PARENT i )] =A[i ].
• For min-heaps (smallest element at root), min-heap property: for all nodes
i, excluding the root, A[PARENT i )] =A[i ].
• By induction and transitivity of =, the max-heap property guarantees that
the maximum element of a max-heap is at the root. Similar argument for
min-heaps.
• HEAPIFY is an important subroutine for manipulating heaps. Its inputs are
an array A and an index i into the array.
•When HEAPIFY is called, it is assumed that the binary trees rooted at
LEFT(i) and RIGHT(i) are heaps, but that A[i] may be smaller than its
children, thus violating the heap property
•. The function of HEAPIFY is to let the value at A[i] "float down" in the
heap so that the subtree rooted at index i becomes a heap.

142
• Heap sort
• MAX-HEAPIFY is important for manipulating max-heaps. It is used to
maintain the max-heap property.
• Before MAX-HEAPIFY, A[i ] may be smaller than its children.
• Assume left and right subtrees of i are max-heaps.
• After MAX-HEAPIFY, subtree rooted at i is a max-heap.
• The way MAX-HEAPIFY works:
• Compare A[i ], A[LEFT i )], and A[RIGHT i )].
• If necessary, swap A[i ] with the larger of the two children to preserve
heap property.
• Continue this process of comparing and swapping down the heap, until
subtree rooted at i is max-heap.
• If we hit a leaf, then the subtree rooted at the leaf is trivially a max-
heap.

143
MAX-HEAPIFY
• Example of a max-heap after building the Heap

144
MAX-HEAPIFY
• The action of HEAPIFY(A, 2), where heap-size[A] = 10.
•The initial configuration of the heap, with A[2] at node i = 2 violating the
heap property since it is not larger than both children.
•The heap property is restored for node 2 in (b) by exchanging A[2] with
A[4], which destroys the heap property for node 4.
•The recursive call HEAPIFY(A, 4) now sets i = 4.

145
MAX-HEAPIFY

• After swapping A[4] with A[9], node 4 is fixed up.

• The recursive call HEAPIFY(A, 9) yields no further change to the data structure.

146
• Building a heap

• A 10-element input array A and the

binary tree it represents
• Build the binary tree from the Array A
• Since i =  n / 2 before the first
iteration, the invariant is initially true
• The figure shows that the loop index i
points
to node 5 , before the call HEAPIFY(A, i)
• i starts off as 5.
• MAX-HEAPIFY is applied to subtrees
rooted at nodes (in order): 16, 2, 3, 1, 4.

147
MAX-HEAPIFY is applied to subtrees rooted at nodes (in order): 16, 2, 3, 1, 4.

148
MAX-HEAPIFY is applied to subtrees rooted at nodes (in order): 16, 2, 3, 1, 4.

149
MAX-HEAPIFY is applied to subtrees rooted at nodes (in order): 16, 2, 3, 1, 4.

150
MAX-HEAPIFY is applied to subtrees rooted at nodes (in order): 16, 2, 3, 1, 4.

151
• The heapsort algorithm

• Given an input array, the heapsort algorithm acts as follows:

• Builds a max- or min- heap from the array.
• Starting with the root (the maximum element), the algorithm places the
maximum element into the correct place in the array by swapping it with
the element in the last position in the array.
• “Discard” this last node (knowing that it is in its correct place) by
decreasing the heap size, and calling MAX-HEAPIFY on the new
(possibly incorrectly-placed) root.
• Repeat this “Discarding” process until only one node (the smallest
element) remains, and therefore is in the correct place in the array.

152
• The heapsort algorithm

153
Example https://www.hackerearth.com/practice/algorithms/sorting/heap-sort/tutorial

• Build Heap

2 3

4 5 6

154
Example
• HEAPIFY: Max Heap

2 3

4 5 6

155
• Heapsort algorithm

Step 1: 8 is swapped with 5.

Step 2: 8 is disconnected from heap as 8 is in correct position now and.

1 1

2 3 2 3

4 5 6 4 5 6

156
• Heapsort algorithm

Step 3: Max-heap is created and 7 is swapped with 3.

Step 4: 7 is disconnected from heap.

1 1

2 3 2 3

4 5 6 4 5 6

157
• Heapsort algorithm

Step 5: Max heap is created and 5 is swapped with 1.

Step 6: 5 is disconnected from heap.

1 1

2 3 2 3

4 4 5 6

5 6
158
• Heapsort algorithm

Step 7: Max heap is created and 4 is swapped with 3.

Step 8: 4 is disconnected from heap.

1
1

2 3 2 3 4 5 6

4 5 6

159
• Heapsort algorithm

Step 9: Max heap is created and 3 is swapped with 1.

Step 10: 3 is disconnected.

1 1 2 3 4

2 3 4 5 6 5 6

160