CS计算机代考程序代写 data structure algorithm COMP2521

COMP2521
Data Structures & Algorithms

Week 9.1
Heaps & Priority Queues

 

1

In this lecture

Why?

Heap structures are tree-like structures used for things like
priority queues – which are really common

What?

Heaps
Heap insert and delete
Priority Queues

2

Heaps
Heaps can be conceptualised as dense tree structures where:

Tree maintains a general order with higher elements up the top
Tree nodes maintain that items on the left are larger, items on right are smaller
New items are added initially at lower-most, right-most leaf, which then  “drift up”
to appropriate level in tree
items are always deleted by removing root (top priority)
Since heaps are dense trees, depth = floor(log2N)+1

 

3 . 1

Heaps

BSTs are typically implemented as linked data structures.
Heaps are often implemented via arrays (assumes we know max size)

Simple index calculations allow navigation through the tree:

left child of Item at index i  is located at 2i
right child of Item at index i  is located at 2i+1
parent of Item at index i  is located at i/2

3 . 2

Heap Structure

typedef struct HeapRep {
Item *items; // array of Items
int nitems; // #items in array
int nslots; // #elements in array
} HeapRep;

typedef HeapRep *Heap;

Heap newHeap(int N)
{
Heap new = malloc(sizeof(HeapRep));
Item *a = malloc((N+1)*sizeof(Item));
assert(new != NULL && a != NULL);
new->items = a; // no initialisation needed
new->nitems = 0; // counter and index
new->nslots = N; // index range 1..N
return new;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4

Heap Inserting
   

Insertion is a two-step process

Add new element at next available position on bottom row
(but this might violate heap property; new value larger than
parent)
Reorganise vales along path to root to restore heap property

5 . 1

Heap Inserting

void HeapInsert(Heap h, Item it) {
// is there space in the array?
assert(h->nitems < h->nslots);
h->nitems++;
// add new item at end of array
h->items[h->nitems] = it;
// move new item to its correct place
fixUp(h->items, h->nitems);
}

// force value at a[i] into correct position
void fixUp(Item a[], int i) {
while (i > 1 && less(a[i/2], a[i])) {
swap(a, i, i/2);
i = i / 2; // integer division
}
}
void swap(Item a[], int i, int j) {
Item tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

5 . 2

Heap Inserting

5 . 3

Heap Deletion
   

Deletion is a three-step process:

Replace root (always root) value by bottom-most, rightmost value
Remove bottom-most, rightmost value
Reorganise values along path from root to restore heap

 

6 . 1

Heap Deletion
Item HeapDelete(Heap h) {
Item top = h->items[1];
// overwrite first by last
h->items[1] = h->items[h->nitems];
h->nitems–;
// move new root to correct position
fixDown(h->items, 1, h->nitems);
return top;
}

// force value at a[i] into correct position
// note that N gives max index *and* # items
void fixDown(Item a[], int i, int N) {
while (2 * i <= N) { // compute address of left child int j = 2 * i; // choose larger of two children if (j < N && less(a[j], a[j+1])) j++; if (!less(a[i], a[j])) break; swap(a, i, j); // move one level down the heap i = j; } } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 6 . 2 Heap Complexity For insertion: Add new item at end of array  ⇒  O(1) Move item up into correct position  ⇒  O(log2n) Summary: O(log(n)) For deletion: Replace root by item at end of array  ⇒  O(1) Move new root down into correct position  ⇒  O(log2n) Summary: O(log(n)) 7 Priority Queue Heap behaviour is exactly behaviour required for Priority Queue : join(PQ,it): ensure highest priority item at front of queue it = leave(PQ): take highest priority item from queue typedef Heap PQueue; void join(PQueue pq, Item it) { HeapInsert(pq,it); } Item leave(PQueue pq) { return HeapDelete(pq); } 1 2 3 4 5 8 . 1 Priority Queue Implementation Comparison 8 . 2 Heap Sort We can use a heap for sorting very easily:   Step 1: build a heap in the array iterates N times, each time doing fixUp() each fixUp() is O(logN),  so overall O(NlogN) Step 2: use heap to build sorted array iterates N times, each time doing swap() and fixDown() swap() is O(1), fixDown() is O(logN), so overall O(NlogN) Cost of heapsort = O(NlogN) 9 Feedback 10