查找最小的k个元素
题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。
*/
/*
<非堆处理>
#include<iostream>
#include <algorithm>
using namespace std;
int main(void)
{
int n, k,j, *a, temp;
cout << “please input numbers and small numbers:”;
cin >> n >> k;
a = (int *)malloc(sizeof(int)*k);
for (int i = 0; i < k; i++)
cin >> a[i];
sort(a,a+k);
for (int i = 0; i < (n – k); i++)
{
cin >> temp;
for (j = 0; j < k&&a[j] < temp; j++);
if (j < k)
{
for (int t = k – 1; t > j; t–)
a[t] = a[t – 1];
a[j] = temp;
}
}
for (int i = 0; i < k; i++)
cout << a[i] << ” “;
cout << endl;
return 0;
}
*/
//<堆处理>
#include<iostream>
using namespace std;
typedef struct node{
int data;
struct node *left;
struct node *right;
}BTnode;
int front, rear;
BTnode *Buy_node(){
BTnode *p;
p = (BTnode *)malloc(sizeof(BTnode));
if (!p) return NULL;
else return p;
}
/*
创建二叉树
*/
BTnode * CreatBTree(BTnode **Q, int *a,int n){
BTnode *root, *t , *p;
root = Buy_node();
if (root == NULL) {
cout << “the space is full!!!” << endl;
return NULL;
}
root->data = a[0];
root->left = root->right = NULL;
Q[++rear] = root;
t = NULL;
for (int i = 1; i < n; i++)
{
if (t == NULL) t = Q[++front];
p = Buy_node();
if (p == NULL) {
cout << “the space is full!!!” << endl;
return NULL;
}
p->data = a[i];
p->left = p->right = NULL;
if (t->left == NULL) t->left = p;
else {
t->right = p;
t = NULL;
}
Q[++rear] = p;
}
return root;
}
/*
给二叉树插入剩下的n-k个值，每次插一个，然后和最大值交换，并调整
*/
BTnode * insertvalue(BTnode ** Q,int value){
BTnode *p;
p = Buy_node();
if (p == NULL) {
cout << “the space is full!!!” << endl;
return NULL;
}
p->data = value;
p->left = p->right = NULL;
if (Q[front]->left&&Q[front]->right){
Q[++front]->left = p;
}
else Q[front]->right = p;
Q[++rear] = p;
return Q[1];
}
/*
调整堆
*/
void siftheap(BTnode ** Q){
int tag = 0,flag,tx;
BTnode *max;
while (!tag){
flag = 0;
for (int t = front; t > 0; t–){
if (Q[t]->left&&Q[t]->right) max = Q[t]->left->data > Q[t]->right->data ? Q[t]->left : Q[t]->right;
else max = Q[t]->left;
if (Q[t]->data < max->data){
tx = Q[t]->data;
Q[t]->data = max->data;
max->data = tx;
flag = 1;
}
if (!flag) tag = 1;
}
}
}
/*
对树排序
*/
void sorttree(BTnode *Q[]){ //排序
int t;
while (rear > 1){
siftheap(Q);
if (Q[front]->right) Q[front]->right = NULL;
else{
Q[front]->right = NULL;
front–;
}
rear–;
}
}
/*
对新插的数据进行处理————与最大值交换，并调整
*/
void fun(BTnode **Q){
int t;
t = Q[1]->data;
Q[1]->data = Q[rear]->data;
Q[rear]->data = t;
if (Q[front]->left&&Q[front]->right) Q[front]->right = NULL;
else { Q[front]->left = NULL;
front–;
}
rear–;
siftheap(Q);
}
/*
输出二叉树
*/
void print(BTnode *root){
if (root){
print(root->left);
cout << root->data << ” “;
print(root->right);
}
}
int main(void)
{
BTnode **Q,*root;
int n, *a, k, temp;
cout << “please input data numbers:”;
cin >> n>>k;
Q = (BTnode **)malloc(sizeof(BTnode )*(n+1));
a = (int *)malloc(sizeof(int)*k);
cout << “please input data value:”;
for (int i = 0; i < k; i++)
cin >> a[i];
front = rear = 0;
root = CreatBTree(Q,a,k);
siftheap(Q);
for (int i = 1; i <= n – k; i++){
cin >> temp;
if (temp < Q[1]->data)
{
root = insertvalue(Q, temp);
fun(Q);
}
for (int i = 1; i <= k; i++)
cout << Q[i]->data << ” “;
cout << endl;
}
root = Q[1];
print(root);
return 0;
}