Skip to content

Instantly share code, notes, and snippets.

@sparfenyuk

sparfenyuk/heap.cpp

Created October 11, 2014 20:37
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save sparfenyuk/8d4edc2a9ff8b3fe0fcf to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save sparfenyuk/8d4edc2a9ff8b3fe0fcf to your computer and use it in GitHub Desktop.
Download ZIP
Heap: insert integer and extract maximum
Raw
heap.cpp
#include <iostream>
#include <iterator>
#include <deque>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
typedef unsigned long long input_type;
size_t get_parent_index(size_t i)
{
if (i % 2 == 0) {
return (i - 1) / 2;
}
return i / 2;
}
size_t get_left_child_index(size_t i)
{
return 2 * i + 1;
}
size_t get_avalaible_leaf_num(deque<input_type>& array)
{
if (!array.empty() && array[0] == 0) {
return 0;
}
return array.size();
}
void insert_at(size_t index, input_type value, deque<input_type>& array)
{
assert(index <= array.size());
if (index == array.size()) {
array.push_back(value);
}
else {
array[index] = value;
}
}
void remove_top(input_type& value, deque<input_type>& array)
{
assert(!array.empty());
value = array.front();
assert(value != 0);
array.front() = 0;
}
void remove_bottom(input_type& value, deque<input_type>& array)
{
assert(!array.empty());
value = array.back();
array.pop_back();
}
bool sift_down(deque<input_type>& array, size_t& index)
{
size_t child_index = get_left_child_index(index);
if (child_index >= array.size()) {
return false;
}
if (child_index + 1 < array.size()) {
if (array[child_index + 1] > array[child_index]) {
child_index++;
}
}
if (array[index] < array[child_index]) {
swap(array[index], array[child_index]);
index = child_index;
return true;
}
return false;
}
bool sift_up(deque<input_type>& array, size_t& index)
{
if (index == 0) {
return false;
}
size_t parent_index = get_parent_index(index);
if (array[index] > array[parent_index]) {
swap(array[index], array[parent_index]);
index = parent_index;
return true;
}
return false;
}
void insert(input_type value, deque<input_type>& array)
{
size_t i = get_avalaible_leaf_num(array);
insert_at(i, value, array);
bool do_sift_down = i == 0;
if (do_sift_down) {
while (sift_down(array, i));
}
else {
while (sift_up(array, i));
}
}
input_type extract(deque<input_type>& array)
{
if (array.empty()) {
return 0;
}
input_type value = 0;
remove_top(value, array);
input_type bottom_value = 0;
remove_bottom(bottom_value, array);
if (bottom_value != 0) {
insert(bottom_value, array);
}
return value;
}
int main()
{
{
deque<input_type> input;
insert(1, input);
insert(1, input);
insert(1000, input);
insert(100, input);
insert(101, input);
insert(10, input);
insert(1, input);
assert(extract(input) == 1000);
assert(extract(input) == 101);
assert(extract(input) == 100);
}
{
deque<input_type> input;
insert(20, input);
assert(extract(input) == 20);
assert(extract(input) == 0);
}
{
deque<input_type> input;
insert(20, input);
insert(2, input);
assert(extract(input) == 20);
assert(extract(input) == 2);
assert(extract(input) == 0);
}
{
deque<input_type> input;
insert(20, input);
insert(10, input);
insert(15, input);
assert(extract(input) == 20);
assert(extract(input) == 15);
}
{
deque<input_type> input;
insert(20, input);
insert(10, input);
insert(15, input);
insert(11, input);
assert(extract(input) == 20);
assert(extract(input) == 15);
}
{
deque<input_type> input;
insert(20, input);
insert(10, input);
insert(15, input);
insert(12, input);
insert(13, input);
insert(14, input);
insert(15, input);
insert(2, input);
assert(extract(input) == 20);
assert(extract(input) == 15);
insert(21, input);
assert(extract(input) == 21);
return 0;
}
size_t n = 0;
cin >> n;
deque<input_type> input;
vector<input_type> output;
for (size_t i = 0; i <= n; ++i) {
string cmd;
if (getline(cin, cmd))
{
if (cmd[0] == 'I') {
input_type value = atoll(&cmd[7]);
insert(value, input);
}
else if (cmd[0] == 'E') {
output.push_back(extract(input));
}
}
}
for (size_t i = 0, size = output.size(); i < size; ++i) {
if (output[0] == 0) {
continue;
}
cout << output[i] << endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment