CLRS-Cpp-Implementations-Chapter-6

 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

#include "../build_max_min_heap/build_max_min_heap.h"
#include "../max_min_heapify/max_min_heapify.h"
namespace CLRS
{
  template <typename T, std::size_t n>
  void heapsort(T (&a)[n])
  {
    CLRS::build_max_heap(a);
    for(std::size_t i = n - 1; i >= 1; --i)
      {
	T temp = a[i];
	a[i] = a[0];
	a[0] = temp;
	if(i >= 2)
	  CLRS::max_heapify(a, 0, i);
      }
  }

  /*
   * use minimal heap priority queue
   * result sorted from large to small.
   */
  template <typename T, std::size_t n>
  void min_heapsort(T (&a)[n])
  {
    CLRS::build_min_heap(a);
    for(std::size_t i = n - 1; i >= 1; --i)
      {
	T temp = a[i];
	a[i] = a[0];
	a[0] = temp;
	if(i >= 2)
	  CLRS::min_heapify(a, 0, i);
      }
  }
}

 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

namespace CLRS
{
  inline std::size_t pre_proc(std::size_t i)
  {
    return ++i;
  }

  inline std::size_t post_proc(std::size_t i)
  {
    return --i;
  }

  inline std::size_t parent(std::size_t i)
  {
    i = pre_proc(i);
    i /= 2;
    return post_proc(i);
  }

  inline std::size_t left(std::size_t i)
  {
    i = pre_proc(i);
    i = 2 * i;
    return post_proc(i);
  }

  inline std::size_t right(std::size_t i)
  {
    i = pre_proc(i);
    i = 2 * i + 1;
    return post_proc(i);
  }
}

 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

#include "../max_min_heapify/max_min_heapify.h"
namespace CLRS
{
  template <typename T, std::size_t n>
  void build_max_heap(T (&a)[n])
  {
    for(long i = n / 2 - 1; i >= 0; --i)
      CLRS::max_heapify(a, i);
  }

  template <typename T>
  void build_max_heap(std::vector<T> &a)
  {
    std::size_t n = a.size();
    for(long i = n / 2 - 1; i >= 0; --i)
      CLRS::max_heapify(a, i);
  }

  template <typename T, std::size_t n>
  void build_min_heap(T (&a)[n])
  {
    for(long i = n / 2 - 1; i >= 0; --i)
      CLRS::min_heapify(a, i);
  }

  template <typename T>
  void build_min_heap(std::vector<T> &a)
  {
    std::size_t n = a.size();
    for(long i = n / 2 - 1; i >= 0; --i)
      CLRS::min_heapify(a, i);
  }
}

 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

#include "../common_heap_utility.h"
namespace CLRS
{
  template <typename T, std::size_t n>
  void max_heapify(T (&a)[n], std::size_t i, std::size_t length = n)
  {
    std::size_t l = CLRS::left(i);
    std::size_t r = CLRS::right(i);
    std::size_t largest = i;
    if(l < length && a[l] > a[i])
      largest = l;
    if(r < length && a[r] > a[largest])
      largest = r;
    if(largest != i)
      {
	T temp = a[i];
	a[i] = a[largest];
	a[largest] = temp;
	max_heapify(a, largest, length);
      }
  }

  template <typename T>
  void max_heapify(std::vector<T> &a, std::size_t i)
  {
    std::size_t l = CLRS::left(i);
    std::size_t r = CLRS::right(i);
    std::size_t largest = i;
    if(l < a.size() && a[l] > a[i])
      largest = l;
    if(r < a.size() && a[r] > a[largest])
      largest = r;
    if(largest != i)
      {
	T temp = a[i];
	a[i] = a[largest];
	a[largest] = temp;
	max_heapify(a, largest);
      }
  }

  template <typename T, std::size_t n>
  void min_heapify(T (&a)[n], std::size_t i, std::size_t length = n)
  {
    std::size_t l = CLRS::left(i);
    std::size_t r = CLRS::right(i);
    std::size_t minimum = i;
    if(l < length && a[l] < a[i])
      minimum = l;
    if(r < length && a[r] < a[minimum])
      minimum = r;
    if(minimum != i)
      {
	T temp = a[i];
	a[i] = a[minimum];
	a[minimum] = temp;
	min_heapify(a, minimum, length);
      }
  }

  template <typename T>
  void min_heapify(std::vector<T> &a, std::size_t i)
  {
    std::size_t l = CLRS::left(i);
    std::size_t r = CLRS::right(i);
    std::size_t minimum = i;
    if(l < a.size() && a[l] < a[i])
      minimum = l;
    if(r < a.size() && a[r] < a[minimum])
      minimum = r;
    if(minimum != i)
      {
	T temp = a[i];
	a[i] = a[minimum];
	a[minimum] = temp;
	min_heapify(a, minimum);
      }
  }
}

 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

#include "../common_heap_utility.h"
#include "../max_min_heapify/max_min_heapify.h"
namespace CLRS
{
  template <typename T>
  // return reference or copy?
  T heap_maximum(const std::vector<T> &a)
  {
    if(a.size() == 0)
      throw(std::logic_error("this queue is empty"));
    return a[0];
  }

  template <typename T>
  T heap_extract_max(std::vector<T> &a)
  {
    if(a.size() == 0)
      throw(std::underflow_error("heap underflow"));
    T max = a[0];
    a[0] = a.back();
    a.pop_back();
    CLRS::max_heapify(a, 0);
    return max;
  }

  template <typename T>
  void max_heap_increase_key(std::vector<T> &a, std::size_t i, T key)
  {
    if(key < a[i])
      throw(std::logic_error("new key is smaller than current key"));
    a[i] = key;
    while(i > 0 && a[CLRS::parent(i)] < a[i])
      {
	T temp = a[CLRS::parent(i)];
	a[CLRS::parent(i)] = a[i];
	a[i] = temp;
	i = CLRS::parent(i);
      }
  }

  template <typename T>
  void max_heap_insert(std::vector<T> &a, T key)
  {
    a.push_back(key);
    max_heap_increase_key(a, a.size() - 1, key);
  }

  // for minimum heap priority queue
  template <typename T>
  // return reference or copy?
  T heap_minimum(const std::vector<T> &a)
  {
    if(a.size() == 0)
      throw(std::logic_error("this queue is empty"));
    return a[0];
  }

  template <typename T>
  T heap_extract_min(std::vector<T> &a)
  {
    if(a.size() == 0)
      throw(std::underflow_error("heap underflow"));
    T min = a[0];
    a[0] = a.back();
    a.pop_back();
    CLRS::min_heapify(a, 0);
    return min;
  }

  template <typename T>
  void min_heap_increase_key(std::vector<T> &a, std::size_t i, T key)
  {
    if(key > a[i])
      throw(std::logic_error("new key is larger than current key"));
    a[i] = key;
    while(i > 0 && a[CLRS::parent(i)] > a[i])
      {
	T temp = a[CLRS::parent(i)];
	a[CLRS::parent(i)] = a[i];
	a[i] = temp;
	i = CLRS::parent(i);
      }
  }

  template <typename T>
  void min_heap_insert(std::vector<T> &a, T key)
  {
    a.push_back(key);
    min_heap_increase_key(a, a.size() - 1, key);
  }
}