1. //
    2. // Created by TeneChang on 2020/10/28.
    3. //
    5. #include "Heap.h"
    6. #include <iostream>
    7. using namespace std;
    9. Heap::Heap(bool _isMaxHeap) {
    10.     IsMaxHeap = _isMaxHeap;
    11. }
    13. Heap::Heap(int _Key[], int _VertexN, bool _IsMaxHeap) {
    14.     IsMaxHeap = IsMaxHeap;
    15.     VertexN = 0;
    16.     for(int i = 1; i <= _VertexN; i++){
    17.         Insert(_Key[i]);
    18.     }
    19. }
    21. void Heap::ShiftUp(int i) {
    22.     if(i == 1)
    23.         return;
    25.     while(i > 1){
    26.         if(Compare(Key[i],Key[i/2])){
    27.             swap(Key[i],Key[i/2]);
    28.         } else break;
    29.         //shift up util it is smaller than its parent or reaches the top
    30.         i = i/2;
    31.     }
    32.     return;
    33. }
    35. void Heap::ShiftDown(int i, int n) {
    36.     //node i is a leaf node
    37.     if(2*i > n)
    38.         return;
    40.     while(2*i <= n){
    41.         //swap with the larger children
    42.         i = 2*i;
    43.         if(i+1 <= n && Compare(Key[i+1],Key[i])){
    44.             i = i+1;
    45.         }
    47.         if(Compare(Key[i],Key[i/2])){
    48.             swap(Key[i],Key[i/2]);
    49.         } else break;
    50.     }
    51.     return;
    52. }
    54. void Heap::Insert(int key) {
    55.     VertexN++;
    56.     Key[VertexN] = key;
    58.     ShiftUp(VertexN);
    59. }
    61. void Heap::Delete(int i) {
    62.     int x = Key[i];
    63.     Key[i] = Key[VertexN];
    64.     VertexN--;
    65.     if(Compare(Key[i],x)) ShiftUp(i);
    66.     else if(Compare(Key[i], x)) ShiftDown(i,VertexN);
    67. }
    69. void Heap::DeleteTop() {
    70.     Delete(1);
    71. }
    73. int Heap::GetTop() {
    74.     return Key[1];
    75. }
    77. void Heap::PrintHeap() {
    78.     for(int i = 1; i <= VertexN; i++)
    79.         cout<<Key[i]<<" ";
    80.     cout<<endl;
    81. }
    83. void Heap::SetValue(int A[], int n) {
    84.     VertexN = n;
    85.     for(int i = 1; i <= n; i++)
    86.         Key[i] = A[i];
    87. }
    90. void Heap::HeapSort() {
    91.     int n = VertexN;
    92.     for(int i = VertexN; i >= 2; i--){
    93.         swap(Key[1], Key[i]);
    94.         ShiftDown(1,--n);
    95.         PrintHeap();
    96.     }
    97. }
    99. void Heap::GetValue(int *A) {
    100.     for(int i = 1; i <= VertexN; i++)
    101.         A[i] = Key[i];
    102. }
    104. bool Heap::Compare(int a, int b) {
    105.     if(IsMaxHeap){
    106.         if(a > b) return true;
    107.         else return false;
    108.     }else{
    109.         if(a < b) return true;
    110.         else return true;
    111.     }
    112. }
    2. #ifndef GREEDYMANNER_DISJOINTSET_H
    3. #define GREEDYMANNER_DISJOINTSET_H
    5. const int MAXSIZE = 20;
    6. class DisjointSet {
    8.     //use array to represent a  forest
    9.     int Forest[MAXSIZE];
    10.     int Rank[MAXSIZE];
    11.     int VertexN;
    13. public:
    14.     DisjointSet();
    15.     DisjointSet(int n);
    17.     void MakeSet(int A[], int R[], int n);
    18.     int Find(int x);
    19.     void Union(int x, int y);
    20.     void PrintDisjointSet();
    22. };
    23. #endif //GREEDYMANNER_DISJOINTSET_H
    26. #include "DisjointSet.h"
    27. #include <iostream>
    28. using namespace std;
    30. DisjointSet::DisjointSet(int n) {
    31.     VertexN = n;
    32.     for(int i = 1; i <= n; i++){
    33.         Forest[i] = i;          //point to the root
    34.         Rank[i] = 0;            //initially, the rank is 0
    35.     }
    36. }
    38. DisjointSet::DisjointSet() {
    40. }
    42. void DisjointSet::MakeSet(int A[], int R[], int n) {
    43.     VertexN = n;
    44.     for(int i = 1; i <= n; i++){
    45.         Forest[i] = A[i];          //point to the root
    46.         Rank[i] = R[i];
    47.     }
    48. }
    50. int DisjointSet::Find(int x) {
    51.     int parent = Forest[x];
    52.     while(parent != Forest[parent]){
    53.         parent = Forest[parent];
    54.     }
    56.     int root = parent;
    57.     parent = x;
    58.     while (parent != Forest[parent]){
    59.         int w = Forest[parent];  //record parent
    60.         Forest[parent] = root;   //point to the root
    61.         parent = w;              //shift up
    62.     }
    64.     return root;
    65. }
    67. void DisjointSet::Union(int x, int y) {
    69.     int root1 = Find(x);
    70.     int root2 = Find(y);
    72.     if(Rank[root1] <= Rank[root2]){
    73.         Forest[root1] = root2;
    74.         if(Rank[root1] == Rank[root2])
    75.             Rank[root2]++;
    76.     } else
    77.         Forest[root2] = root1;
    78. }
    80. void DisjointSet::PrintDisjointSet() {
    82.     for(int i = 1; i <= VertexN; i++){
    83.         cout<<"("<<i<<","<<Forest[i]<<","<<Rank[i]<<")"<<" ";
    84.     }
    85.     cout<<endl;
    86. }