• API
• FAQ
• Tools
• Archive
daily pastebin goal
57%
SHARE
TWEET

# ASD Heap

icatalin Jan 17th, 2019 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2.
3. class Heap
4. {
5.     int v[100];
6.     int n;//numarul de noduri
7.     void pushUp(int position);
8.     void pushDown(int position);
9. public:
10.     Heap()
11.     {
12.         n = 0;
13.     }
14.     Heap(int *v2, int n2);//construieste un heap pe baza vectorului v2
15.     void insert (int value);//insereaza un element cu valoarea value si ii face pushUP
17.
19.     {
20.         if (n != 0)
21.             return v[1];
22.     }
23.
24.     int *sort();//sorteaza vectorul aka HeapSort
25.     void print();
26. };
27.
28. void swap(int &first, int &second)
29. {
30.     int aux = first;
31.     first = second;
32.     second = aux;
33. }
34.
35. Heap::Heap(int *v2, int n2)
36. {
37.     for (int i = 1; i <= n2; i++)
38.         v[i] = v2[i];
39.
40.     for(int i = n/2; i >= 1; i++) //de la primul nod care nu e frunza, apelez pushDown
41.         pushDown(i);
42. }
43.
44. void Heap::pushUp(int position)
45. {
46.     while (position != 1 && v[position] > v[position / 2])
47.         swap(v[position], v[position / 2]);
48.     position = position / 2;
49. }
50.
51. void Heap::pushDown(int position)
52. {
53.     int maximPosition = position;//pozitia fiului cel mai mare
54.
55.     if ( 2 * position <= n && v[position] < v[2 * position])//compar cu fiul stang
56.         maximPosition = 2 * position;
57.
58.     if (2 * position + 1 <= n && v[2 * position + 1 ] > v[maximPosition])//compar cu fiul drept
59.         maximPosition = 2 * position + 1;
60.
61.     if (position != maximPosition)
62.     {
63.         swap(v[position], v[maximPosition]);
64.         pushDown(maximPosition);
65.     }
66. }
67.
68. void Heap::insert(int value)
69. {
70.     n++;
71.     v[n] = value;
72.     pushUp(n);
73. }
74.
76. {
77.     swap(v[1], v[n]);//interschimb radacina cu ultima frunza
79.     pushDown(1);
80. }
81.
82. int *Heap::sort()
83. {
84.     int nAux = n;
85.         for (int i = 1; i <= nAux; i++)
86.         {
88.         }
89.     n = nAux;
90.     return v;
91. }
92.
93. void Heap::print()
94. {
95.     for (int i = 1; i <= n; i++)
96.         std::cout<<v[i]<<' ';
97.     std::cout<<'\n';
98. }
99.
100. int main()
101. {
102.     Heap heap1;
103.     heap1.insert(90);
104.     heap1.insert(50);
105.     heap1.insert(70);
106.     heap1.insert(40);
107.     heap1.insert(35);
108.     heap1.insert(30);
109.     heap1.insert(60);
110.     heap1.insert(12);
111.     heap1.print();
112.     heap1.sort();
113.     heap1.print();
114.     return 0;
115. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top