DevJourney · code I wrote while learning
main.cpp
1.9 KB#include <iostream>
using namespace std;
class Node {
public:
int freq;
Node *left, *right;
};
Node *heap[100];
int heapSize = 0;
Node *newNode(int f) {
Node *temp = new Node();
temp->freq = f;
temp->left = temp->right = NULL;
return temp;
}
void swap(Node *&a, Node *&b) {
Node *t = a;
a = b;
b = t;
}
void heapifyUp(int i) {
while (i > 0 && heap[(i - 1) / 2]->freq > heap[i]->freq) {
swap(heap[i], heap[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
void heapifyDown(int i) {
int smallest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < heapSize && heap[l]->freq < heap[smallest]->freq)
smallest = l;
if (r < heapSize && heap[r]->freq < heap[smallest]->freq)
smallest = r;
if (smallest != i) {
swap(heap[i], heap[smallest]);
heapifyDown(smallest);
}
}
void insert(Node *node) {
heap[heapSize] = node;
heapifyUp(heapSize);
heapSize++;
}
Node *extractMin() {
Node *root = heap[0];
heap[0] = heap[heapSize - 1];
heapSize--;
heapifyDown(0);
return root;
}
void printCodes(Node *root, int arr[], int top) {
if (root->left) {
arr[top] = 0;
printCodes(root->left, arr, top + 1);
}
if (root->right) {
arr[top] = 1;
printCodes(root->right, arr, top + 1);
}
if (!root->left && !root->right) {
for (int i = 0; i < top; i++)
cout << arr[i];
cout << " ";
}
}
int main() {
int n;
cin >> n;
int freq[100];
for (int i = 0; i < n; i++)
cin >> freq[i];
for (int i = 0; i < n; i++)
insert(newNode(freq[i]));
while (heapSize > 1) {
Node *left = extractMin();
Node *right = extractMin();
Node *parent = newNode(left->freq + right->freq);
parent->left = left;
parent->right = right;
insert(parent);
}
int arr[100];
printCodes(heap[0], arr, 0);
return 0;
}