# 2.1. Heap-based Priority Queues and Heap Sort

# A Variety of Priority Queue Implementations

[Priority Queue 1: Max(Min) Heap]
[Priority Queue 2: Min-Max Heap]
[Priority Queue 3: Heap and Hashing]
[Priority Queue 4: Deap]
[Priority Queue 5: Leftist Tree]
[Priority Queue 6: Binomial Heap]
[Priority Queue 7: Fibonacci Heap]

# [Job Scheduling Example: Priority Queue]

Consider the following sequence of requests in an operating system:

# Requirement 1

CPU executes the process with the highest priority first.
Use a heap structure – a simple max heap :)

typedef struct _process {
  int proc_id; 
  char *owner; 
  int priority;
} Process;

static Process *_proc_heap; 
static int _proc_heap_size = 0; 
static int _proc_heap_ptr = 0;

int PH_create(int n);        
int PH_full();
int PH_empty();
int PH_insert(Process item);
int PH_delete(Process *item);

# Requirement 2

The priority of processes can be modified after they are placed in the priority queue.
```
int H_change_priority(int proc_id, int new_priority);
```
- This function requires locating a particular process in the heap, but the basic heap operations provide no efficient way to do it.
- Employ an auxiliary data structure such as a hash table that keeps track of the location of each process in the heap structure.
Once the two requirements are satisfied, the operating system can process the following basic commands efficiently:
```
INSERT  <proc_id>  <owner>  <priority>
DELETE
CHANGEPR <proc_id> <new_priority> PRINTHEAP
END
```

alg