查找最小的K个元素,使用最大堆。

时间:2022-03-05 07:43:26

查找最小的K个元素,使用最大堆,具体代码如下:

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
void swap(int *a, int *b)
{     int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
void heap_adjust(int *a, int i, int size)
{
    int lchild = 2 * i;
    int rchild = 2 * i + 1;
    int max = i;
    if (i <= size / 2) //大于size/2的为叶子节点,不需要调整
    {         if (lchild <= size && a[lchild]>a[max])
            max = lchild;
        if (rchild <= size && a[rchild]>a[max])             max = rchild;
        if (max != i)
        {
            swap(&a[i], &a[max]);
            heap_adjust(a, max, size); //依此调整下面的子树,为了防止交换之后不满足堆的性质
        }
    }
} void create_heap(int *a, int size)
{
    int i = 0;
    for (i = size / 2; i >= 1; i--)
        heap_adjust(a, i, size);
} void heap_sort(int *a, int size)
{
    int i = 0;
    int temp = 0;
    create_heap(a, size);
    for (i = size; i >= 1; i--)
    {         swap(&a[i], &a[1]);
        heap_adjust(a, 1, i - 1);
    }
} int main(int argc, char **argv)
{
    int a[100];
    int size = 0;
    int nTemp = 0;
    cout << "堆个数:";
    while (scanf("%d", &size) == 1 && size >0)
    {
        int i = 0;
        for (i = 1; i <= size; i++)
            scanf("%d", &a[i]);
        heap_sort(a, size);
        printf("请输入要显示的K\n");
        scanf("%d", &nTemp);
        for (i = 1; i <= nTemp; i++)
            printf("%d ", a[i]);
    }
    return 0;
}

运行效果如图1所示:

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAqUAAAELCAIAAABvRGhmAAAQIUlEQVR4nO3d748c50EH8P1z7g/Ie7+0MAIOpQYiVPnAqtRDCAlZVAKBLECoaU1a2rrCDoSQlKaRCQlnN4rTNM6dK+jRJFLP1CXGAnpFaitydz7bobbpi+PF2uvZmWeendkf8+w+9/noq+pub3bm2XF63/l9vcvnl0VERCTv9C6fX97fXBUREZGx8+3l5XlI3fD0vYiIyBSSvOn1vYiIyMyTvOn1vYiIyMyTvOn1vYiIyMyTvOn1vYiIyMyTvOn1vYiISIssRdW9K3nT63sREZEW6bjvDw4ODg4O4q901/eb//ipN1/6/Sb59mu/t/fPn0z+ryUiIjJeIqU+o/37YsFPUvZT6PtXXrv43nevv/fd71Vy/f2t6+9vXb/45tWLlzcuXt546cKr//XmbyT/1xJZiFw6ubR09Ni1sX6aZEhWlxyGdN/3g5qfsOyn0PdX1jfuP3hw7/6I3H/w4K0rGx98/UTyfy3JLNdOPzF8RO2Js2vBKY+fWlo6dW7W4wkspTLCh5ZPx/7vMHGBhT9v49U13kIXd3WJNEqSvp98z346fb9x9eoH//7fTz935TPPv/3ZF7555u/eeuZr3/j+9/9zb3fnh9vbP9ze3t3deXbt3WfX3tX3MotcO/3E0K/ytWPLS0tLJ49Xp6z5pT/5dsDQHGLVcu5I836dvMCC0zRfXeMttG3mZ3WJNMmh3r9f37h64+aPPvm5i6tfXPvtc6/+znOv/O6LF7a2bu7t/E+x759741/0vcwi5QLbXO0XcGB3cO3YcqA/ptz3NUtZ3d/svMBCI2mxusZbaNvMz+qSTNP22rqRcxvjR9Pas098/v4b33znxs0f/dGLb/7WuVc+/qW/ferL5586f3Zr6+bezofb29vb2z/Y3d158eq3vvbuFX0vs0iowPrHhI9c2lzd3zxx9ujgd/2Js0eHiq106Pjxj/p7vX1DMz9+6tHL/YIPzaG8lMcJF9iJs0cHM+iPeXV/UFHFkRT2wssFFh5wYCSjVlfs40eHVN5oKI/w3JHCWjp+9ujgvfOzuioJTdb/Fy9sIB4/VVxWwzlLhyn3/CPTnVt8nlM8jJ/y+vx+3z955rmfe/pLv/D5v1j+8p8/+ezT/f377e0f9Pfv/+Ff31j7t4v6XmaRYIEV9hqLfd+vkEKxba4G9u+Haqb49qFKu3R6sNDgHEpLqc55MP4joWWtXjo53Blrx5aLSz9Z+lDBAQdGMmp1xeYWHVKs70sd+XA+g46cn9VVu/TKsgpbkMMfpMGc5fBlwuP500rd8Nr1/c+f+eIvfuFzv/yXZz7215/+tRf/pL9/Pzief/3H16//+Lq+l1mkvsCCR+mrR+9Lr5w4e3R4gkEXjj/PRxl5gLrQfJdOLgWquvjTQuWEBxwayajVFZtbdEiRvq+eLxiuyTlaXQ3+Myh8ouHjIg3nLIcxyZt+mn3/S2efefL8Z37lb/7sqa/88cdf/sOtrZu7hfP3D+7fe3D/nr6XWWT0DutwLp0sXZ5WPfseMOjC0HHaQF1VlrK6v1lbYA/3TYePUQdOORfe/vinsQEHRjJidUXnFh1Sfd8HtpNKfT9Hq6vBfwbFCQrDazhnOZRJ3vTT7PuP/dWnf/WFP/31r54+ceEPfvPVT21t3dz58FHf7+x89NHd/Vu39L3MIo1OSBdT3hQI9H3sd/Tg1/rR+uP5gaWs7m8GC6x/QcCjoZZ2WBsX2KgBP17oiNUVndvs+n6OVle7/wzKfa/dJZjkTT+lvn97/dr3/uOzr104s/byM5e++vnXv/KFN174zneuDfp+58MP79ze393d1fcyi7S/4Lx0gViprZtdrH7uSGHXLXg4OnQZWrXAhl8pH4Ie3mQpVlr0aHlsJKNWV2xu0SGFdtlrRzh8jdt8ra4W/wkNr8ymtznIIUzypp9O319+652f/ez/7tzeu7O/d2d/7+6dO3fv7N+9feveT//3/r2ffvTR3du3b9+6tXfr1p6+l1mkXGD968Afd0ngsqn4r+nyBdhrx5b7c1s7dmow2VDxhH/RB5o1XGCPlvVwl7FYYKVrwcJ3+dcOODSSUasrNrfRQxra8y5dTPf4g5fnMy+ra2grZMR6CG3ljPyHkEOb5E0/nb7/+5eff+vKRjVvr3/rnav/9PY7VwevvPzS8zde1/cy5VQex1Y6jB+8THp4j/zRrWJDO8EDpRvSHgr00FJoL7b+yv/K+I8eu1Y5QH2pMJLirEqHr+sGXB3JqNU16uPXD2noTrmTx0sjLJ50P3Wucjx/LlZXeVTByUrbLqUHFo36hxCZxzTt+59sfOLG6yc++Pro3Hj9xE82PpH8g4ns110gtphLWayR7G+uBs7fz+MgRQ5L/D1cyTrd3Cs1P3dkzc9INusvbZurQYocmuh7EZlOrp1+onSBpGPdIvMTfS8iU8vQTfMO2ovMU/S9iIhI/tH3IiIi+Uffi4iI5B99LyIikn/0vYiISP7R9yIiIvlnRN+/d+EpERERWZSM3/e9Xq/X662vr/cK+t+WXoxoOGV1suaLAICcHBwc7Lc0q76vvl4nPll1bm3nDwCZWby+b3IwoDhNcUp9D8DhlL7v1+tVh9uqvIPH8+PzB4AszUXfB7+uanI+PrLpMN0dfRsTACyQrvs+vh8fqcm6H0UOA5Rqfop9X2306gdR+QDMj5T794P/jW8E9Cr13PDb0hdT6fvICIuL0/cAzJW6vl9ZWZl538e/HrwSfLFusvicg/v6Y4j0fd0GAQAkFOz7lUfS931Qk8mC01S3CcYT7/vgBACQULXvV4Z10fdBkUFHfhqfVV3ft63nur4v7eU3nyEAzFSp74s1X1f5C7B/H5ln3X7/tPp+vBkCwEwF+77u22n2fXFXeDCaqfR9vOCnUsN1fR+ZAAASqvZ99fD+NPu+7hh79euIkX1f3M+uvnGS4/nrFXU/ajI3AOhGgvvx6o6ER6q0pEmbBucwed8DwCJKc/990RhFO/Itg/6e8EACAOQht76v7qlH9unbLhcAFlT6vgcAZk3fA0D+Dg4O3m9D3wPA4tH3AJC/BH3vJnUA6FjXfV+seZUPAN3Q9wCQP30PAPlLfP5e3wNAB5Jdn6/sAaAz+h4A8pem75U9AHQp5fn71J8dAA4Lz9cDgPzpewDIn74HgPzpewDIn74HgPzpewDI38HBwX5L+h4AFkyCvvfwfADoWNd97+/jAUD39D0A5C9N3/drXt8DQDecvweA/CU7nq/yAaAzzt8DQP70PQDkz/l7AMif5+sBQP70PQDkT98DQP70PQDkT98DQP70PQDkT98DQP6S/b0cd+EDQGdSPl+v5xF7ANAJfQ8A+Ut8/l7fA0AHUva9sgeAbiTre2UPAJ1J0/fKHgC6pO8BIH/6HgDy5/l6AJA/fQ8A+dP3AJA/fQ8A+dP3AJA/fQ8A+dP3AJC/lPffuwUfALqRoO81PQB0rOu+V/YA0D19DwD5S9P3zt8DQJdS7t+rfADohr4HgPzpewDIX7L78ZQ9AHTG8/UAIH/6HgDyp+8BIH/6HgDyp+8BIH/6HgDyp+8BIH+Jn5/vFnwA6IC/jwcA+dP3AJA/fQ8A+Ut8/j71xweAQyHl9fkqHwC6oe8BIH8pz9/rewDoRoL9e+fvAaBjnq8HAPnT9wCQP30PAPnT9wCQP30PAPnT9wCQP30PAPnzfD0AyF+yvvfIHQDoTJq+94g9AOhSsufp9hzPB4Cu+Hs5AJC/NH1fknolAEDmXJ8PAPnT9wCQv/T346l8AJg1z9cDgPzpewDIn74HgPzpewDIn74HgPzpewDIn74HgPwl+3s57rwHgM74ezkAkD/P0wWA/Ol7AMhfmr53/h4AumT/HgDyp+8BIH+uzweA/Ln/HgDy5/l6AJA/fQ8A+dP3AJA/fQ8A+dP3AJA/fQ8A+dP3AJA/998DQP48Xw8A8qfvASB//l4OAOQvWd8rewDoTJq+V/YA0KVk1+en/uAAcIi4Xg8A8pem792CDwBd8nw9AMifvgeA/Ol7AMifvgeA/Ol7AMifvgeA/Ol7AMhfyufnp/vUAHC4eH4+AOQv5fP1Un92ADgs7N8DQP70PQDkT98DQP70PQDkT98DQP5SXp+v9QGgG56vBwD50/cAkD99DwD50/cAkD99DwD50/cAkD99DwD5S9D37r8HgI6led7OYPEqHwA6kLLv7eIDQDeS9b1D+gDQmZR933M8HwA6kfLv5fT0PQB0Ilnf9xev7wGgA67PB4D8uf8eAPLn+XoAkD99DwD50/cAkL856vvIufzgj5qc+1/c6wOqI1/czwJAcmmu1wsOpVXfFx/aEzdymvVmmr9rjEU0/8gAMIY0+/frlUfoxysw8m2TFmzelM3nXPfTqbRywy0AAGgocd8XNdkzDk42sggXq+/rNn1GHhIAgDrpz9+P3LnvDR8PqL5l8Erdh2yyQRDX6i3xZY20HjqYEXyxOIzitxMOAID8pO/7gbqimrDAgn1Zt4j10P59Xd/HZzW2Vn3fG+54fQ9A0Fw8Pz++o1wqvOCedKTk0vZ9/ANGPm9pDpGlDCYITgkAvbk6fx9UbcHgdsDkfd+kiRu+pfmHavLT4HaAvgeglfR9H6/M6uut+r6uIyNaVeYY8x85ZXxtBJfbfFMDgMNpLvq+NKZgbxWrrlr/k/R9cIOjSek2/HqSKesmrvZ98QsAKJmLvo+Ua2myXqXzIn0/skpHvmXkZsTkfd/22+Dc9D0AcXPR96Ux1W0NlH469b5vWPbVpQcH1mrOzbcGgtMXF63yAahK2ffFvdKS4hBLzVqarK7v62ov8npwq6JOXd83GUm8wlv1fXXY+h6AqmR933xvuPRi8I1NOnLkj4pja9iakTGM/WJ86ycyBwCoM1/H8+t2kXv1fV+3nx0R3xqo23UuvdhE3aLjI4xsuzR5OwBUpX++XqTegq8POq+6BRB5e3VupXfVNXTzeTY04dyUPQBjSN/3AMCs6XsAyJ++B4D86XsAyF+yv48Xv0QOAJiiNH2f+lMDwOGi7wEgf/oeAPKX+Px96o8PAIdCyuvzVT4AdEPfA0D+Up6/1/cA0I0E+/fO3wNAxzxfDwDyp+8BIH/6HgDyp+8BIH/6HgDyp+8BIH/6HgDyl/j+++a34LeastXMx34egEcIALAoEv99vIaV2ba8m79r7Of9eWQQAAuk1PcrKyuldq++MuXn6cYrc7yd9erXbd/bZEp9D8CiqPZ9seBL306z71tV5njNOqO+L32EtqMCgO4F+77f8cWvZ9L3vRkczx/vLeNteeh7ABZF9fz9yrCZnL9vu4s8uyPzbd+1HtJ2QQDQseD1epGyn1rf9xc/i74fu4O72aoAgO7VXZ9fV/ZTO57fN/W+b7sxMcnxeX0PwKKY9/vv2x48H+Nge6uJJ3wXACTh+XoAkD99DwD50/cAkL+u+15EREQWJWP2vYiIiGQQfS8iIpJ/9L2IiEj+0fciIiL5R9+LiIjkH30vIiKSf/S9iIhI/tH3IiIi+edh34uIiEje+X9b1rCu1CUFKQAAAABJRU5ErkJggg==" alt="" />

图1 运行效果