Question

I have few questions to be ask for search in computer:

1) Draw a min heap with at least 8 nodes.

2) What are two real life examples of a Priority Queue?

3) Draw a min heap with at least 8 nodes.

r

Answer 1

Draw a min heap with at least 8 nodes.

A heap data structure in computer science is spacial tree that satisifies the heap property, this just means that the parent is less than or equal to child node for a minimum heap A.K.A min heap.

Build a min heap : Let's take an array and make a heap with an empty heap using the wiliams method. We will insert the values 3,1,6,5,2,4,7 and 8. in our heap.

3

1

6

5

2

4

7

8

array

To add an element to a heap we must perform an up-heap operation(also known as bubbe-up, precolated-up,sift-up trickle-up,heapify-up, or cascade-up), by following this alogrithm:

1. If heap is emptu place element at root.
2. Add the element to the bottom level of heap .
3. Compare the added element with its parent; if they are in the correct order, stop.
4. If not, swap the element with its parent and return to the previous step.

First Insert 3 in root of the empty heap:

What are two real life examples of a Priority Queue?

• Prim's algorithm implementaion cn be done using priority queues.
• Dijkstra's shortest path alogrithm implementation can be done using queues.
• Priority queues are used to sort heaps.
• priority queuesare used in operating system for loading balance and interrupt handling.
• priority queues are used in huffman codes for data compression.
• In traffic light,depending upon the traffic, the colors will be given priority

Real example for priority queue:

Printer .

Each traffic light in our simulation would have an event scheduled for its next change. When a light changes to red, we schedule it's next change to green some bnumber of seconds later. When a light changes to green, we scheduled a change to yellow event some time a lttle later, and so on.

Each moving car on the street would have an event associated with the time it it needs to reach the next intersection along it's path. When it reaches that intersection, we schedule a new event for the intersection after that, and so on.

All scheduled event could be kept in a priority queue ordered on the time at which the event is scheduled. The main logic of the silumation is simply

while(simulation has not ended)

{

get next event form the priority queue;

trigger that event;

}