0 / 0 / 0
Регистрация: 01.12.2015
Сообщений: 120
1

Организовать структуру данных Heap для хранения целых чисел

07.05.2016, 12:09. Показов 6333. Ответов 1
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Помогите пожалуйста решить задачую Заранее спасибо!
В этой задаче вам необходимо организовать структуру данных Heap для хранения целых чисел, над которой определены следующие операции:

a) Insert(k) – добавить в Heap число k ;
b) Extract достать из Heap наибольшее число (удалив его при этом).

Входные данные
В первой строке содержится количество команд N (1 ≤ N ≤ 100000), далее следуют N команд, каждая в своей строке. Команда может иметь формат: “0 <число>” или “1”, обозначающий, соответственно, операции Insert(<число>) и Extract. Гарантируется, что при выполенении команды Extract в структуре находится по крайней мере один элемент.

Выходные данные
Для каждой команды извлечения необходимо отдельной строкой вывести число, полученное при выполнении команды Extract.

Примеры
входные данные
10
0 941
0 6077
1
0 9560
1
0 12770
1
0 2117
0 1791
1
выходные данные
6077
9560
12770
2117
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.05.2016, 12:09
Ответы с готовыми решениями:

Как правильно организовать структуру хранения данных
Добрый день! Прошу совета по базам данных. есть задача логистики деталей со склада на участок и...

Как организовать массив для хранения данных?
не судите только начал изучать с++ , правильно ли так сохранять все данные в массив? const...

Определите структуру Complex для хранения комплексных чисел
Помоги пожалуйста не могу разобраться. Нужно определить типы и функции и в функции main()...

Определите структуру Complex для хранения комплексных чисел
Не могу осилить задание, помогите! Определите структуру Complex для хранения комплексных чисел: ...

1
193 / 100 / 131
Регистрация: 23.06.2015
Сообщений: 249
08.05.2016, 13:01 2
Лучший ответ Сообщение было отмечено Derzky как решение

Решение

Pascal
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
72
73
74
75
76
77
78
79
program task;
var
  heap : array[0..100007] of longint;
  heap_free : longint;
 
procedure add(x : longint);
begin
  heap[heap_free] := x;
  inc(heap_free);
end;
 
procedure remove;
begin
  dec(heap_free);
end;
 
procedure heap_insert(x : longint);
var 
  ii, parent, temp : longint;
begin
  add(x);
  ii := heap_free - 1;
  parent := (ii - 1) div 2;
  while((ii > 0) and (heap[parent] < heap[ii])) do begin
    temp := heap[ii];
    heap[ii] := heap[parent];
    heap[parent] := temp;
 
    ii := parent;
    parent := (ii - 1) div 2;
  end;
end;
 
procedure heapify(x : longint);
var 
  left_child, right_child, largest_child, temp: longint;
begin
  while(true) do begin
    left_child := 2 * x + 1;
    right_child := 2 * x + 2;
    largest_child := x;
    
    if((left_child < heap_free) and (heap[left_child] > heap[largest_child])) then largest_child := left_child;
    if((right_child < heap_free) and (heap[right_child] > heap[largest_child])) then largest_child := right_child;
    if(largest_child = x) then break;
 
    temp := heap[x];
    heap[x] := heap[largest_child];
    heap[largest_child] := temp;
    x := largest_child;
  end;
end;
 
function extract : longint;
var 
  res : longint;
begin
  res := heap[0];
  heap[0] := heap[heap_free- 1];
  remove;
  heapify(0);
  extract := res;
end; 
 
var 
  n, id, x, i : longint;
begin
  heap_free := 0;
  
  readln(n);
  for i := 1 to n do begin
    read(id);
    if(id = 0) then begin
      readln(x);
      heap_insert(x);
    end
    else if(id = 1) then writeln(extract);
  end;
end.
0
08.05.2016, 13:01
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.05.2016, 13:01
Помогаю со студенческими работами здесь

Определите структуру Complex для хранения комплексных чисел
Условия задачи: Определите структуру Complex для хранения комплексных чисел: struct Complex ...

Определите структуру Complex для хранения комплексных чисел
Я чего-то совсем запутался, может кто поможет. =определить типы и функции в соответствии с...

Реализовать структуру данных для хранения координат прямоугольника
Ребята, помогите... Зачет по ОПП. Задание - реализовать структуру данных для хранения координат...

Для хранения данных о ноутбуках описать структуру NOTEBOOK
Для хранения данных о ноутбуках описать структуру вида (при необходимости дополнив ее): ...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru