求一计算机数据结构题解

发布网友发布时间：2023-09-11 10:33

共2个回答

热心网友时间：2023-09-17 16:49

以最大堆为例,给一个建堆的算法,
楼主要的保持堆的性质的算法,只要选取其中一段程序就行了~~~

//******************
// 6.3_1 建堆
// Date 2007.02.13
//******************

#include <iostream>
using namespace std;

const int maxn = 1000;

void max_heapify( int A[maxn], int i, int heap_size )
{
int l, r, largest, temp;

l = 2 * i;
r = 2 * i + 1;

if (( l <= heap_size ) && ( A[l] > A[i] ))
largest = l;
else
largest = i;
if (( r <= heap_size ) && ( A[r] > A[largest] ))
largest = r;
if ( largest != i ) {
temp = A[i];
A[i] = A[largest];
A[largest] = temp;

max_heapify( A, largest, heap_size );
}
}

void build_max_heap( int A[maxn], int n )
{
int i;

for (i = n / 2; i >= 1; i--)
max_heapify( A, i, n );
}

int main()
{
int i, n;
int A[maxn];

cin >> n;

for (i = 1; i <= n; i++)
cin >> A[i];

build_max_heap( A, n );

for (i = 1; i < n; i++)
cout << A[i] << ' ';

cout << A[n] << endl;

return 0;
}

热心网友时间：2023-09-17 16:50

算法很简单阿，以最大堆为例：
1. top = n+1;
2. top = top/2; if(top == 0) return;
3. top_lchid = top*2, top_rchid=top*2+1;
取(top_lchid,top_rchid)大者，如果其大于k(top)则与k(top)交换；
4. 转到2。

//C代码：
#include <stdio.h>
#include <time.h>

static const int BUFLEN = 1024;

void getHeap(int heap[], int n)
{
if(n <= 0) return;
int top = (n-1)/2;
int left , right;
while(1)
{
left = top *2+1;
right = top *2+2;
if(right<=n && heap[right]>heap[left] )
{
if(heap[right]<=heap[top]) break;
heap[top] = heap[top] + heap[right];
heap[right] = heap[top] - heap[right];
heap[top] = heap[top] - heap[right];
}
else if(heap[left]>heap[top])
{
heap[top] = heap[top] + heap[left];
heap[left] = heap[top] - heap[left];
heap[top] = heap[top] - heap[left];
}
else break;
if(top == 0) break;
top = (top-1)/2;
}
}//12 35 46 25 32 1 5 64 58 48 125 478 254 365 123 456 458 456 -1

void main()
{
int heap[BUFLEN];
int data,n = -1;
printf("Input a numbers(end with -1):");
while(n<BUFLEN)
{
scanf("%d", &data);
if(data < 0) break;
heap[++n] = data;
getHeap(heap,n);
printf("Result Heap: ");
for(int i=0; i<n; ++i) printf("%d,",heap[i]);
printf("%d\n",heap[n]);
}
printf("Result Heap: ");
for(int i=0; i<n; ++i) printf("%d,",heap[i]);
printf("%d\n",heap[n]);
}