# 2.2. PQ1: Max(Min) Heap (1)

ref. [Horowitz 5.6.2] [Neapolitan 7.6]
Problem
- The following operations must be performed as mixed in data processing:
  - Store a record with a key in an arbitrary order.
  - Fetch the record with the current largest key.
A solution
- Design a data structure that offers an efficient implementation of the following operations:
Insert an element with an arbitrary key.
Delete an element with the largest key.

# An Array Implementation

Ref. [Sedgewick 9.2]

void PQinit();
int PQempty();
void PQinsert(int);
int PQdelmin();
void PQdec(int);

#include<stdlib.h> 
static int *pq;
static int N;
#define MAX_N 10000;

void PQinit(){
    pq = malloc(MAX_N * sizeof(int));
    N = 0;
}
int PQempty(){
    return N == 0;
}
void PQinsert(int v){
    pq[N++] = v;
}

int PQdelmin(){
    int j, min = 0;
    for (j = 1; j < N; j++)
        if (less(pq[min], pq[j]))
            min = j;
    exch(pq[min], pq[N - 1]);
    return pq[--N];
}

int less(int i, int j){
    return **... * *;
}

void exch(int i, int j){
    ...
}

void PQdec(int k){
    ...
}

What will be the worst-case time complexity of each operation?

# Max(Min) Heap: Definitions

# Definition 1

[Horowitz 5.6.2] [Neapolitan 7.6]
A max(min) heap is a complete binary tree where the key value in each internal node is no smaller(larger) than the key values in its children.

# Definition 2

A binary tree has the max(min) heap property if and only if
- The number of nodes of the tree is either 0 or 1, or
- 2 For the tree that has at least two nodes, the key in the root is no smaller(larger) than that in each child and the subtree rooted at the child has the max(min) heap property.
A max(min) heap is a complete binary tree that has the max(min) heap property.

# Brainstorming on Max Heap Operations

Max Heap Example
Deletion Example 1
Deletion Example 2
Insertion Example

Deletion from a Max Heap

#define MAX_ELEMENTS 200
#define HEAP_FULL(n) (n == MAX_ELEMENTS-1) #define HEAP_EMPTY(n) (!n)
typedef struct {
int key;
/* other fields */
} element;
element heap[MAX_ELEMENTS]; 
int n = 0;

ref. [Horowitz 5.6.2]

C = log_2 n

//최대 히프에 삽입
void insert_max_heap(element item, int* n){
int i;
if(HEAP_FULL(*n)){
  fprintf(stderr,"the heap is FULL\n");
  exit(1);
}
i=++(*n);
while((i != 1) && (item.key > heap[i/2].key)){
  heap[i] = heap[i/2];
  i/=2;
}
heap[i] =item;
}

element delete_max_heap(int* n){
int parent,child;
element item,temp;
if(HEAP_EMPTY(*n)){
  fprintf(stderr,"the heap is EMPTY\n");
  exit(1);
}

item=heap[1];
temp=heap[(*n)--];
parent = 1;
child = 2;
while(child <= *n){
  if(child< *n) && (heap[child].key) < heap[child+1].key
   child++;
  if(temp.key >= heap[child.key) break;

  heap[parent] =heap[child];
  parent=child;
  child* = 2;
}
heap[parent] = temp;
return item;
}

O(log n)

# Another Heap Implementation (Min Heap)

ref. [Sedgewick 9.3]

void PQinit(int);
int PQempty();
void PQinsert(int);
int PQdelmin();
static int *pq;
static int N;
void PQinit(int maxN){
    pq = malloc(maxN * sizeof(int));
    N = 0;
}

int PQempty() { 
    return N == 0; 
}

void PQinsert(int v){
    pq[++N] = v;
    fixUp(pq, N);
}

Item PQdelmin(){
    exch(pq[1], pq[N]);
    fixDown(pq, 1, N - 1);
    return pq[N--];
}

fixUp(int a[], int k){
    while (k > 1 && a[k / 2] > a[k]){
        exch(a[k], a[k / 2]);
        k = k / 2;
    }
}

fixDown(int a[], int k, int N){
    int j;
    while (2 * k <= N){
        j = 2 * k;
        if (j < N && a[j] > a[j + 1])
            j++;
        if (a[k] <= a[j])
            break;
        exch(a[k], a[j]);
        k = j;
    }
}

What will be the worst-case time complexity of each operation?

alg