Scribd
Upload
1 views3 pages

Priority Queue Notes

The document explains the process of building a min-heap using the numbers 10, 5, 20, 3, and 15, detailing each insertion step and the necessary comparisons and swaps to maintain the min-heap property. It also introduces the concept of a double-ended priority queue (DEPQ) and its operations, including insertion, finding minimum and maximum values, and deletion of minimum and maximum elements. The min-max heap structure is described, emphasizing the alternating levels of min and max ordering.

Uploaded by

E.THANUSREE
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
1 views3 pages

Priority Queue Notes

The document explains the process of building a min-heap using the numbers 10, 5, 20, 3, and 15, detailing each insertion step and the necessary comparisons and swaps to maintain the min-heap property. It also introduces the concept of a double-ended priority queue (DEPQ) and its operations, including insertion, finding minimum and maximum values, and deletion of minimum and maximum elements. The min-max heap structure is described, emphasizing the alternating levels of min and max ordering.

Uploaded by

E.THANUSREE
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Build a min-heap step by step  3 goes to the left child of 10

using the numbers: 10, 5, 20, 3, (next available spot).


15.
 Compare with parent (10).
A min-heap is a binary tree Since
where:
 3 < 10, swap.
 The root is always the
 Now 3 is child of 5.
smallest element.
Compare with parent (5).
 Each parent node is less Since 3 < 5, swap again.
than or equal to its
3
children.
/ \
 It is a complete binary
tree (all levels filled except 5 20
possibly the last, filled left
/
to right).
10
 Step 1: Insert 10
10 Step 5: Insert 15

Step 2: Insert 5  15 goes to the right child of


10 (next available spot).
 5 goes to the left child of
10.  Compare with parent (10).
Since 15 > 10, no swap.
 Compare with parent (10).
Since 5 < 10, swap. Final Min-Heap:

5 3

/ / \

10 5 20

Step 3: Insert 20 /\

 20 goes to the right child of 10 15


5.  Root (3) is the minimum
 Compare with parent (5). element.
Since 20 > 5, no swap.  Every parent is smaller than
5 its children.

/\  Tree is complete (filled left


to right).
10 20

Step 4: Insert 3
 Removes the root node.

 Replaces it with the last


element and trickles down
A double-ended priority queue
to restore heap order.
(DEPQ) supports efficient access
to both the minimum and 5. DeleteMax()
maximum elements. The most
 Removes the maximum
common implementation is a
child of the root.
min-max heap, which is a
complete binary tree with  Replaces it with the last
alternating levels of min and max element and trickles down
ordering. to restore heap order.

🔧 Operations in a Double- 🧩 Insertions into the Given


Ended Priority Queue Min-Max Tree

1. Insert(x) Initial Tree Root: 7

 Adds a new element x to 7 (min)


the structure.
/ \
 Maintains the min-max
70 (max) 40 (max)
heap property:
/ \ / \
o Even levels (starting
from root) are min 30 9 10 15
levels.
/\ /\ /
o Odd levels are max
45 50 30 20 12
levels.
Insert 5
 After insertion at the
bottom, the element is  Insert at the next available
bubbled up to its correct spot (right child of 15).
position based on its level.
 5 is at level 3 (min level).
2. FindMin()
 Compare with parent (15).
 Returns the root node Since 5 < 15, bubble up.
(minimum element).
 Compare with grandparent
3. FindMax() (40). Since 5 < 40, bubble
up again.
 Returns the maximum
among the root’s children  Compare with root (7).
(usually one of the first two Since 5 < 7, bubble up
children). again.

4. DeleteMin()
New root becomes 5, and
the tree restructures to maintain
min-max levels.

Insert 80

 Insert at the next available


spot.

 80 is at level 3 (min level).

 Compare with parent. If 80


> parent, no bubble up.

 Compare with grandparent


(max level). If 80 >
grandparent, bubble up to
max level.

80 will settle in a position


where it maintains the min-max
heap property, likely under a
max-level node.

You might also like