#include <iostream>
// URL : https://yougome.tistory.com/481
#define swap(a,b) {register int t = (a);(a)=(b);(b)=t;}
using namespace std;
class minheap {
private:
int * tree;
int size;
int idx;
private:
void sizeup() {
const int old_size = size;
int * old_tree = tree;
size = size + size;
tree = new int[size];
memset(tree, 0, sizeof(int) * size );
for( register int i = 0; i < old_size; i++ )
tree[i] = old_tree[i];
delete old_tree;
}
public:
minheap(int size_t):size(size_t), idx(0) {
tree = new int[size_t];
memset(tree, 0, sizeof(int) * size_t );
}
~minheap(){
delete tree;
}
void insert( int v ) {
if( idx + 2 >= size ) sizeup();
tree[++idx] = v;
int c = idx;
int p = c/2;
int t = 0;
while(p > 0 && tree[p] > tree[c] ) {
swap(tree[p], tree[c]);
p = (c = p)/2;
}
}
int pop() {
if( idx < 1 ) return -1;
int p = 1;
int l = p + p;
int r = l + 1;
int tar = l;
int t = 0;
int ret = tree[1];
tree[1] = tree[idx--];
while( l < idx+1 ) {
if( r + 1 >= size && tree[p] < tree[l] ) break;
if( tree[p] < tree[l] && tree[p] < tree[r]) break;
if( r + 1 >= size ) tar = l;
else tar = tree[l] < tree[r] ? l : r;
swap(tree[tar],tree[p]);
r = 1 + ( l = ( p = tar ) + p );
}
return ret;
}
void print() {
cout << " size( " << size << " )-> " ;
for( register int i = 1; i < idx+1; i++ ) {
cout << tree[i] << "," ;
}
cout << endl;
}
};
int main() {
minheap mh(3);
int arr[] = { 10, 3,2,3,4,5,2,2,3,3,5,5,3,50,30,44,20,10,3,4,5,6,77,2,3,34,4,4,5,5,6,7,4,2,2,3,3,3,4,3,45,6,7,8,9,9,4,4,23,33,43,2,12,34,44,3,3355,6,6,77,7,8,5,65,4,1,2,65};
int s = sizeof( arr )/sizeof(int);
int popCnt = 0;
cout << "inputs : ";
for( register int i = 0; i < s*3; i++ ) {
mh.insert(arr[i%s]);
cout << arr[i%s] << ", " ;
}
cout << endl;
mh.print();
cout << "min: ";
register int i = 0;
int lv = 0;
for( i = 0; i < s*2; i++ ) {
if( (lv = mh.pop()) > -1 ) {
popCnt++;
cout << lv << ",";
}
}
cout << endl;
cout << "popCnt:" << popCnt << " , i:" << i << " s:" << s << " lastPop:" << lv << endl;
mh.print();
char * aa;
getchar();
return 0;
}
inputs : 10, 3, 2, 3, 4, 5, 2, 2, 3, 3, 5, 5, 3, 50, 30, 44, 20, 10, 3, 4, 5, 6,
77, 2, 3, 34, 4, 4, 5, 5, 6, 7, 4, 2, 2, 3, 3, 3, 4, 3, 45, 6, 7, 8, 9, 9, 4, 4
, 23, 33, 43, 2, 12, 34, 44, 3, 3355, 6, 6, 77, 7, 8, 5, 65, 4, 1, 2, 65, 10, 3,
2, 3, 4, 5, 2, 2, 3, 3, 5, 5, 3, 50, 30, 44, 20, 10, 3, 4, 5, 6, 77, 2, 3, 34,
4, 4, 5, 5, 6, 7, 4, 2, 2, 3, 3, 3, 4, 3, 45, 6, 7, 8, 9, 9, 4, 4, 23, 33, 43, 2
, 12, 34, 44, 3, 3355, 6, 6, 77, 7, 8, 5, 65, 4, 1, 2, 65, 10, 3, 2, 3, 4, 5, 2,
2, 3, 3, 5, 5, 3, 50, 30, 44, 20, 10, 3, 4, 5, 6, 77, 2, 3, 34, 4, 4, 5, 5, 6,
7, 4, 2, 2, 3, 3, 3, 4, 3, 45, 6, 7, 8, 9, 9, 4, 4, 23, 33, 43, 2, 12, 34, 44, 3
, 3355, 6, 6, 77, 7, 8, 5, 65, 4, 1, 2, 65,
size( 384 )-> 1,1,1,2,2,2,2,2,2,2,2,2,2,3,3,2,2,2,2,3,2,3,3,3,2,3,3,4,4,5,3,5,2
,2,2,3,3,3,3,3,4,2,3,4,4,4,3,4,5,2,3,3,3,5,6,8,4,5,6,7,30,5,6,7,7,4,2,10,3,3,3,3
,3,3,3,3,3,4,5,3,4,5,5,6,3,3,3,5,6,8,6,4,5,4,9,4,5,7,5,4,2,43,3,34,4,12,4,34,45,
44,7,50,9,3355,9,6,23,33,43,77,12,34,44,8,3355,6,6,77,65,44,8,65,10,4,2,65,65,20
,10,4,4,5,3,10,3,4,5,5,5,50,30,44,20,10,3,4,5,6,77,5,4,34,4,50,30,45,6,44,7,20,4
,10,5,7,4,8,45,6,7,9,9,77,9,77,23,33,43,34,12,34,44,5,3355,6,6,77,23,8,6,65,33,7
,4,65,
min: 1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3
,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4
,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6
,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,8,
popCnt:136 , i:136 s:68 lastPop:8
size( 384 )-> 8,8,8,9,8,8,9,9,10,20,9,9,12,33,12,9,10,10,20,23,30,45,23,20,33,1
2,43,44,34,30,34,43,10,10,33,10,30,65,34,65,34,34,50,65,77,77,44,77,34,50,65,44,
23,77,44,65,3355,45,50,44,44,45,3355,65,43,77,77,3355,
