這些天復習算法。
heap_tree.h
1 //Author: sheppard(ysf1026@gmail.com) 2013-04-06
2 // Desc:
3
4 #ifndef __Atmlib_HeadTree_H__
5 #define __Atmlib_HeadTree_H__
6
7 #include <vector>
8
9 class HeapTree
10 {
11 protected:
12 std::vector<int> data_;
13 int heap_size_;
14
15 protected:
16 virtual void HeapFix(int index) = 0;
17
18 void Swap(int index1, int index2);
19
20 public:
21 HeapTree(int* array, int length);
22
23 int heap_size() const;
24 void PrintHeapData();
25 void PrintData();
26
27 int GetRightSonIndex(int index);
28 int GetLeftSonIndex(int index);
29 int GetParentIndex(int index);
30
31 void BuildHeapTree();
32 virtual void Insert(int value) = 0;
33 };
34
35 class MaxHeapTree : public HeapTree
36 {
37 protected:
38 void HeapFix(int index);
39 public:
40 MaxHeapTree(int* array, int length):HeapTree(array, length){}
41 void Insert(int value);
42 int ExtractMax();
43 void IncreaseKey(int index, int new_value);
44 };
45
46 #endif
heap_tree.cpp
1 //Author: sheppard(ysf1026@gmail.com) 2013-04-06
2 // Desc:
3
4 #include <iostream>
5 #include "heap_tree.h"
6
7 HeapTree::HeapTree(int* array, int length)
8 {
9 heap_size_ = length;
10 for(int i=0; i!=length; ++i)
11 data_.push_back(array[i]);
12 }
13
14 int HeapTree::heap_size() const
15 {
16 return heap_size_;
17 }
18
19 void HeapTree::PrintHeapData()
20 {
21 for(int i=0; i!=heap_size_; ++i)
22 {
23 std::cout<<data_[i]<<" ";
24 }
25 std::cout<<std::endl;
26 }
27
28 void HeapTree::PrintData()
29 {
30 for(int i=0; i!=data_.size(); ++i)
31 {
32 std::cout<<data_[i]<<" ";
33 }
34 std::cout<<std::endl;
35 }
36
37 int HeapTree::GetRightSonIndex(int index)
38 {
39 return (index + 1) * 2;
40 }
41 int HeapTree::GetLeftSonIndex(int index)
42 {
43 return GetRightSonIndex(index) - 1;
44 }
45 int HeapTree::GetParentIndex(int index)
46 {
47 return index / 2 - (index%2==0 ? 1 : 0);
48 }
49
50 void HeapTree::BuildHeapTree()
51 {
52 if(0 == data_.size())
53 return;
54 int i = GetParentIndex(data_.size()-1);
55 for(; i!=-1; --i)
56 {
57 HeapFix(i);
58 }
59 }
60
61 void HeapTree::Swap(int index1, int index2)
62 {
63 int tmp = data_[index1];
64 data_[index1] = data_[index2];
65 data_[index2] = tmp;
66 }
67
68 void MaxHeapTree::HeapFix(int index)
69 {
70 if(index >= heap_size())
71 return;
72 int left = GetLeftSonIndex(index);
73 int right = GetRightSonIndex(index);
74 int largest = index;
75
76 if(left<heap_size() && data_[left]>data_[largest])
77 largest = left;
78 if(right<heap_size() && data_[right]>data_[largest])
79 largest = right;
80
81 if(largest == index)
82 return;
83
84 Swap(largest, index);
85 HeapFix(largest);
86 }
87
88 void MaxHeapTree::Insert(int value)
89 {
90 //TODO
91 }
92
93 int MaxHeapTree::ExtractMax()
94 {
95 if(heap_size_ < 1)
96 {
97 //TODO: assert?
98 return -1;
99 }
100
101 int max = data_[0];
102 data_[0] = data_[heap_size_-1];
103 HeapFix(0);
104 return max;
105 }
106
107 void MaxHeapTree::IncreaseKey(int index, int new_value)
108 {
109 //TODO
110 }
heap_sort.h
1 //Author: sheppard(ysf1026@gmail.com) 2013-04-06
2 // Desc:
3
4 #ifndef __Atmlib_HeapSort_H__
5 #define __Atmlib_HeapSort_H__
6
7 #include "heap_tree.h"
8
9 class HeapSort : public MaxHeapTree
10 {
11 private:
12 void Sort();
13
14 public:
15 HeapSort(int* array, int length);
16 };
17
18 #endif
heap_sort.cpp
1 //Author: sheppard(ysf1026@gmail.com) 2013-04-08
2 // Desc:
3
4 #include "heap_sort.h"
5
6 HeapSort::HeapSort(int* array, int length):MaxHeapTree(array, length)
7 {
8 BuildHeapTree();
9 Sort();
10 }
11
12 void HeapSort::Sort()
13 {
14 for( ; --heap_size_>0; )
15 {
16 Swap(0, heap_size_);
17 HeapFix(0);
18 }
19 }