Sheppard Y

 1 //Author: sheppard([email protected]) 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

  1 //Author: sheppard([email protected]) 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 }

 1 //Author: sheppard([email protected]) 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

 1 //Author: sheppard([email protected]) 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 }