Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.83
Nyto4ka
0 / 0 / 0
Регистрация: 10.05.2010
Сообщений: 22
#1

Реализация двоичной кучи(пирамиды)!!! - C++

06.01.2011, 16:26. Просмотров 3120. Ответов 1
Метки нет (Все метки)

Горит расчетная работа на тему "Пирамиды"(другое название "двоичная куча"). Нужно реализовать эту структуру данных, добавление и удаление элементов, и поиск. Реализация пирамиды в виде массива есть, а со всем остальным проблема. ПОМОГИТЕ ПОЖАЛУЙСТА!

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 #include <stdio.h>
const long int MaxV = 5000;
long int a[MaxV];//массив для временного хранения элементов
long int n,i;//
//Our heap variables
long int heap[MaxV];//основной массив нашей кучи
long int nheap, tmp;//размер нашей кучи(количество элементов, находящихся на данный момент в куче)
 /*инициализация кучи*/  
  void InitHeap(void){
    nheap = 0;//обнуляем текущее количество элементов
}
  /*"исправление" кучи*/
        void MoveUp(long int ind){
long int k;
k = ind / 2;
if( ind > 1 ){
if( heap[ind] < heap[k] ){
tmp = heap[ind];
heap[ind] = heap[k];
heap[k] = tmp;
MoveUp(k);
}
}
}
 /*добавление элемента в кучу*/         void HeapAdd(long int x){
nheap++;
heap[nheap] = x;
MoveUp(nheap);
}
       void MoveDown(long int ind){
long int k;
k = ind * 2;
if(k <= nheap){
     if( (k+1 <= nheap) && (heap[k] > heap[k+1]) ) k++;
if( heap[ind] > heap[k] ){
tmp = heap[ind];
heap[ind] = heap[k];
heap[k] = tmp;
MoveDown(k);
}
}
}
 
          long int ExtractMin(void){
long int value;
value = heap[1];
heap[1] = heap[nheap];
heap[nheap] = 0;
nheap--;
MoveDown(1);
return value;
}
 
int main(void){
InitHeap();
printf("Insert (N)umber of elements:\n");
scanf("%d",&n);
printf("Insert array, please:\n");
for(i=0; i<n; i++){
scanf("%d",&tmp);
HeapAdd(tmp);
}
for(i=0; i<n; i++){
a[i] = ExtractMin();
}
printf("Sorted array is:\n");
for(i=0; i<n; i++) printf("%d ",a[i]);
printf("\n");
fflush(stdin);
getchar();
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.01.2011, 16:26
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Реализация двоичной кучи(пирамиды)!!! (C++):

Получать различные начала кучи при создании кучи внутри цикла - C++
Можно ли как-то такое провернуть, чтобы на каждой итерации цикла получались различные адреса (выбираются ОС) на начало кучи (периодические...

Повреждение кучи - C++
#ifndef _TASK2_H_ #define _TASK2_H_ #include &lt;iostream&gt; using namespace std; namespace TeamResult { static int...

Повреждние кучи - C++
Понимаю, тема стара как мир, но похожих случаев не нашел, к сожалению. Есть консольное приложение, в котором реализуется СУБД библиотеки...

Ошибка кучи - C++
Выдает ошибку: &quot;ОС Windows инициировала точку останова в Lab2.exe.Это может быть вызвано повреждением кучи и указывает на ошибку в Lab2.exe...

Размер кучи - C++
С помощью какой библиотечной ф-ции или как узнать размер кучи в языке Си?

Ошибка кучи - C++
Здравствуйте, уважаемые программисты. Возникла у меня такая проблема: Задали сделать курсовую работу на С++ через MFC. Суть задачи: В...

1
v1m
Сообщений: n/a
18.10.2011, 22:06 #2
вот описание и реализация кучи http://olympiads.comoj.com/2011/10/binary-heap/
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.10.2011, 22:06
Привет! Вот еще темы с ответами:

Повреждение кучи - C++
После выполнения программы выдаёт ошибку Debug Assertion Failed Помогите найти и исправить место из-за которого ошибка, я так понимаю она...

Повреждение кучи - C++
Приветствую! Сделал, казалось бы, простую программу, но у меня возникает ошибка на самом ровном месте: void print(node** graph, int V) ...

Повреждение кучи - C++
Есть код #include &lt;iostream&gt; using namespace std; struct STUDENT { char NAME; int GROUP; int SES; };

Границы кучи - C++
Как корректно определить границы кучи в любой момент времени без использования функций менеджера дрп в си? Добавлено через 18 часов 7...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru