Jun
23
一般数据结构上用败者树来实现,这东西我没写过,所以暂时忽略之。
改用相对比较熟悉的heap来处理,写了一个class heap。
为了方便采用一个 5 x 5 的数组来存储需要归并的数据;很容易可以扩展到不定长的不同数据组。
明天再试着写一下败者树。
代码如下:
转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
改用相对比较熟悉的heap来处理,写了一个class heap。
为了方便采用一个 5 x 5 的数组来存储需要归并的数据;很容易可以扩展到不定长的不同数据组。
明天再试着写一下败者树。
代码如下:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct node_t{
int v, i;
bool operator<(const node_t &a)const{
return (v < a.v);
}
bool operator>(const node_t &a)const{
return (v > a.v);
}
friend inline ostream & operator << (ostream &os, const node_t &t){
os << t.v << " @ " << t.i;
return os;
}
};
template<typename T, class cmp = less<T> >
class heap{
public:
T d[500];
int n;
heap(){n = 1;}
heap(int t, T a[]){
init(t, a);
}
void init(int t, T a[]){
d[0] = 0;
for (int i = 0; i < t; ++i){
d[i+1] = a[i];
}
n = t + 1;
makeheap();
}
int size(){return (n - 1);}
void makeheap(){
for (int i = n / 2; i > 0; --i){
siftdown(i);
}
}
void siftdown(int i){
if(i < 1 || i >= n) return;
while(2 * i < n){
i *= 2;
if(i + 1 < n && cmp()(d[i], d[i+1])) i++; //选了大的
if(cmp()(d[i/2], d[i])) swap(d[i/2], d[i]);
else break;
}
}
void siftup(int i){
if(i < 1 || i >= n) return;
while (i >= 1){
if(cmp()(d[i/2], d[i])) swap(d[i/2], d[i]);
else break;
i /= 2;
}
}
void dump(int i = 1, int dep = 0){
if(i >= n) return;
for (int j = 0; j < dep; ++j) printf(" ");
cout << d[i] << endl;
dump(2 * i, dep + 1);
dump(2 * i + 1, dep + 1);
}
T remove(int i){
T a = d[i];
if(i < 1 || i >= n) throw(-4);
d[i] = d[n-1];
n--;
if(cmp()(d[i], a)){
siftdown(i);
}else{
siftup(i);
}
return a;
}
T removetop(){
return remove(1);
}
void insert(T a){
d[n++] = a;
siftup(n - 1);
}
};
int main(){
int a[][5] = {
{7,8,10,13,14},
{0,3,6,12,19},
{2,4,5,7,10},
{15,17,19,21,23},
{5,8,9,20,22}
};
int b[25], bi = 0;
int idx[5];
heap<node_t, greater<node_t> > h;
for (int i = 0; i < 5; ++i){
h[i].v = a[i][0];
h[i].i = i;
idx[i] = 1;
}
h.n = 6;
h.makeheap();
node_t tmp;
while(h.n > 1){
tmp = h.removetop();
printf("~<FROM a[%d][%d]> %d\n", tmp.i, idx[tmp.i]-1, tmp.v);
b[bi++] = tmp.v;
if(idx[tmp.i] < 5){
tmp.v = a[tmp.i][idx[tmp.i]++];
h.insert(tmp);
}
}
for (int i = 0 ; i< 25; ++i){
printf("%d ", b[i]);
if(i % 5 == 4) puts("");
}
return 0;
}
#include <algorithm>
#include <cstring>
using namespace std;
struct node_t{
int v, i;
bool operator<(const node_t &a)const{
return (v < a.v);
}
bool operator>(const node_t &a)const{
return (v > a.v);
}
friend inline ostream & operator << (ostream &os, const node_t &t){
os << t.v << " @ " << t.i;
return os;
}
};
template<typename T, class cmp = less<T> >
class heap{
public:
T d[500];
int n;
heap(){n = 1;}
heap(int t, T a[]){
init(t, a);
}
void init(int t, T a[]){
d[0] = 0;
for (int i = 0; i < t; ++i){
d[i+1] = a[i];
}
n = t + 1;
makeheap();
}
int size(){return (n - 1);}
void makeheap(){
for (int i = n / 2; i > 0; --i){
siftdown(i);
}
}
void siftdown(int i){
if(i < 1 || i >= n) return;
while(2 * i < n){
i *= 2;
if(i + 1 < n && cmp()(d[i], d[i+1])) i++; //选了大的
if(cmp()(d[i/2], d[i])) swap(d[i/2], d[i]);
else break;
}
}
void siftup(int i){
if(i < 1 || i >= n) return;
while (i >= 1){
if(cmp()(d[i/2], d[i])) swap(d[i/2], d[i]);
else break;
i /= 2;
}
}
void dump(int i = 1, int dep = 0){
if(i >= n) return;
for (int j = 0; j < dep; ++j) printf(" ");
cout << d[i] << endl;
dump(2 * i, dep + 1);
dump(2 * i + 1, dep + 1);
}
T remove(int i){
T a = d[i];
if(i < 1 || i >= n) throw(-4);
d[i] = d[n-1];
n--;
if(cmp()(d[i], a)){
siftdown(i);
}else{
siftup(i);
}
return a;
}
T removetop(){
return remove(1);
}
void insert(T a){
d[n++] = a;
siftup(n - 1);
}
};
int main(){
int a[][5] = {
{7,8,10,13,14},
{0,3,6,12,19},
{2,4,5,7,10},
{15,17,19,21,23},
{5,8,9,20,22}
};
int b[25], bi = 0;
int idx[5];
heap<node_t, greater<node_t> > h;
for (int i = 0; i < 5; ++i){
h[i].v = a[i][0];
h[i].i = i;
idx[i] = 1;
}
h.n = 6;
h.makeheap();
node_t tmp;
while(h.n > 1){
tmp = h.removetop();
printf("~<FROM a[%d][%d]> %d\n", tmp.i, idx[tmp.i]-1, tmp.v);
b[bi++] = tmp.v;
if(idx[tmp.i] < 5){
tmp.v = a[tmp.i][idx[tmp.i]++];
h.insert(tmp);
}
}
for (int i = 0 ; i< 25; ++i){
printf("%d ", b[i]);
if(i % 5 == 4) puts("");
}
return 0;
}
欢迎扫码关注:
转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。