cpp_heap_kata/heap_utils.cpp at master · LaurentBERTHOLLE/cpp_heap_kata · 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
#include "heap_utils.h"

#include <iostream>
#include <algorithm>

using namespace std;

void print(const vector<int>& v)
{
    int i = 0;
    for_each(v.begin(), v.end(), [](int e) { cout << e << " "; });
    cout << endl;
}

int getParentIndex(int currentIndex)
{
    return (currentIndex - 1) / 2;
}

int getLeftChildIndex(int currentIndex)
{
    return 2*currentIndex + 1;
}

int getRightChildIndex(int currentIndex)
{
    return 2*currentIndex + 2;
}

void sift_up(vector<int>& v, int currentIndex)
{
    while (currentIndex > 0)
    {
        int parentIndex = getParentIndex(currentIndex);

        if (v[parentIndex] >= v[currentIndex]) return;
        swap(v[parentIndex], v[currentIndex]);
        currentIndex = parentIndex;
    }
}

void sift_down(vector<int>& v, int heap_size)
{
    int currentIndex = 0;
    while (true)
    {
        int leftChildIndex = getLeftChildIndex(currentIndex);
        if (leftChildIndex > heap_size) return;

        int rightChildIndex = getRightChildIndex(currentIndex);
        if (rightChildIndex <= heap_size
                && v[currentIndex] < v[rightChildIndex]
                && v[rightChildIndex] > v[leftChildIndex])
        {
            swap(v[currentIndex], v[rightChildIndex]);
            currentIndex = rightChildIndex;
        }
        else
        {
            if (v[currentIndex] < v[leftChildIndex])
            {
                swap(v[currentIndex], v[leftChildIndex]);
                currentIndex = leftChildIndex;
            }
            else
            {
                return;
            }
        }
    }
}


void heapify(vector<int>& v)
{
    if (v.size() == 0) return;

    cout << "Heapifying: " << endl;
    for (int heapSize = 0; heapSize < v.size(); ++heapSize)
    {
        sift_up(v, heapSize);
        print(v);
    }
}

void sort(vector<int>& v)
{
    cout << "Sorting: " << endl;
    for (int endIndex = v.size()- 1; endIndex >= 0; --endIndex)
    {
        swap(v[0], v[endIndex]);
        sift_down(v, endIndex -1);
        print(v);
    }
}