HuffmanCoding/priorityqueue.cpp at master · aacohn84/HuffmanCoding · GitHub

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include "priorityqueue.h"

priorityqueue::priorityqueue(void)
{
}


priorityqueue::~priorityqueue(void)
{
}

/* Inserts a key,value pair into the priority queue */
void priorityqueue::insert(hist_elem item)
{
	if (heap.heapsize >= 3.0/4 * heap.length())
		heap.grow();

	// place the item at the bottom of the heap
	heap[++heap.heapsize] = item;

	// if heap property is violated, bubble up
	int i = heap.heapsize / 2;
	while (i >= 1 && heap[i].key < item.key)
	{
		swap(heap[i], item);
		i /= 2;
	}
}

/* removes the highest priority key,value pair, returns the value of the pair */
hist_elem priorityqueue::popMax()
{
	if (heap.heapsize < 1)
		throw "Error: heap underflow.";

	hist_elem max = heap[1];
	heap[1] = heap[heap.heapsize];
	heap.heapsize -= 1;
	maxHeapify(1);

	return max;
}

/* used to maintain the heap property */
void priorityqueue::maxHeapify(int i)
{
	int largest, l, r;
	bool exchange = false;

	do
	{
		if (exchange)
		{
			swap(heap[i], heap[largest]);
			i = largest;
		}

		l = left(i);
		r = right(i);

		if (l <= heap.heapsize && heap[l].key > heap[i].key)
			largest = l;
		else
			largest = i;

		if (r <= heap.heapsize && heap[r].key > heap[largest].key)
			largest = r;

	} while (exchange = largest != i);
}

/* used to maintain the heap property */
void priorityqueue::minHeapify(int i)
{
	int smallest, l, r;
	bool exchange = false;

	do
	{
		if (exchange)
		{
			swap(heap[i], heap[smallest]);
			i = smallest;
		}

		l = left(i);
		r = right(i);

		if (l <= heap.heapsize && heap[l].key < heap[i].key)
			smallest = l;
		else
			smallest = i;

		if (r <= heap.heapsize && heap[r].key < heap[smallest].key)
			smallest = r;

	} while (exchange = smallest != i);
}

/* returns the offset index of the left child of i */
int priorityqueue::left(int i)
{
	return 2*i;
}

/* returns the offset index of the right child of i */
int priorityqueue::right(int i)
{
	return 2*i + 1;
}

void priorityqueue::swap(hist_elem &a, hist_elem &b)
{
	hist_elem copy_a = a;
	a = b;
	b = copy_a;
}