30 / 14 / 7
Регистрация: 08.01.2019
Сообщений: 636
1

Как реализовать бинарную кучу (пирамиду)?

03.11.2019, 16:53. Показов 7660. Ответов 30

Author24 — интернет-сервис помощи студентам
Доброго времени суток всем. Продолжаю изучать структуры данных, пришла очередь деревьев бинарного поиска, а именно бинарная куча(пирамида). Помогите пожалуйста разобраться в этом.
Как инициализировать узел кучи, саму кучу?
Добавление/удаление элемента пользователем пирамиды
Вывод кучи на экран*
Найти и вывести на экран значение максимального элемента*
Как перебирать вершины дерева( обход дерева)?
Как сортировать кучу?**

В общем можно, пожалуйста, простейший вариант реализации макс-кучи с комментариями, чтобы разобраться во всем этом. Пожалуйста, очень хочу разобраться.

Куча это ориентированный граф или неориентированный?
Все деревья реализуются на основе массивов? Массив более выгодный из-за того, что нужно обращаться

**Элементы сначала записываются в массив рандомно/пользователем, после добавляются в кучу при помощи симметричного обхода, я прав? Как это сделать?)
*Везде картинки деревьев с выводом через пользовательский интерфейс, мне тоже так нужно, так что еще три вопроса:
1. Как это делать?
2. Для этого лучше создать новую тему или оставить вопрос открытым под этой темой?
3. Реализация кучи отличается от реализации кучи с использованием виндовс форм, если да то насколько? В плоть до количества аргументов подаваемых в метод? Тип если делать под виндовс форм то все изначально делается по другому или что?) Ответьте как можно детальней, плз, я си шарп учу ток второй месяц
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.11.2019, 16:53
Ответы с готовыми решениями:

Как добавить в код бинарную сериализацию
Есть программа using System; using System.Collections.Generic; using System.Linq; using...

Как сделать бинарную сериалиацию в массив байтов?
Делаю сетевую игру. Решил делать связь между клиентами с помощью сериализации: есть класс с данными...

Реализовать бинарную кучу на базе указателей
И всем доброго времени суток, форумчане! Ситуация следующая. Реализовать бинарную кучу на базе...

Проверить, может ли массив представлять бинарную кучу
Задан массив из N чисел. Необходимо проверить, может ли он представлять бинарную кучу.

30
30 / 14 / 7
Регистрация: 08.01.2019
Сообщений: 636
11.11.2019, 15:23  [ТС] 21
Author24 — интернет-сервис помощи студентам
Цитата Сообщение от Enifan Посмотреть сообщение
изменить тип данных, с которым будет работать список
Я это сделал в первую очередь
C#
1
2
3
4
5
private List<KeyValuePair<double, string>> list;
        public BinaryHeap()
        {
            list = new List<KeyValuePair<double, string>>();
        }
0
1842 / 1184 / 501
Регистрация: 14.10.2018
Сообщений: 3,180
11.11.2019, 15:40 22
Vlast001, сам список работает не с даблом и строкой, а со структурой KeyValuePair
C#
1
2
list.Add(value,data); 
list.Add(new KeyValuePair(12.3, "string"));
0
352 / 247 / 76
Регистрация: 18.03.2016
Сообщений: 979
11.11.2019, 16:14 23
Vlast001,
Цитата Сообщение от Vlast001 Посмотреть сообщение
Ты не доволен тем, что я в вопросительном предложении поставил знак вопроса или что?
Если ты это все так видишь и у тебя нет желания объяснять то - иди засорять собою в другое место. Раз тебе больше нечего написать
Почему я должен помогать тебе?
Что ты сам сделал?

Ты разобрался как работает куча?
написал сам алгоритм для кучи?

весь код в этой теме написал Enifan.

возможно нарисовать это не простая задача, но я не увидел даже твоих попыток
кроме этой)
Цитата Сообщение от Vlast001 Посмотреть сообщение
Я нашел единственную штуку которая заработала (в отличие от бесчисленного множества копированный примеров пикчербокса которые так ничего в форме и не нарисовали )
C#
1
2
3
4
5
protected override void OnPaint(PaintEventArgs e)
        {
            base.OnPaint(e);
            e.Graphics.DrawEllipse(Pens.Red, 20, 20, 50, 50);
        }
ты в курсе что можно было поискать в гугле что такое куча, её реализации на шарпе
потом можно было поискать примеры визуализации деревьев

вместо этого ты просишь сделать за тебе и прокомментировать всё...
0
1842 / 1184 / 501
Регистрация: 14.10.2018
Сообщений: 3,180
11.11.2019, 16:30 24
Цитата Сообщение от jester Посмотреть сообщение
весь код в этой теме написал Enifan
Уверяю что данный пользователь сделал достаточное кол-во ошибок, ему еще самому есть что поучить
Цитата Сообщение от jester Посмотреть сообщение
просишь сделать за тебе и прокомментировать всё...
Главное чтобы он чему нибудь научился. Лично я делая данное задание узнал что то новое для себя, возможно когда нибудь напишу качественную бинарную кучу с разными вариациями, доведя ее до ума.
0
352 / 247 / 76
Регистрация: 18.03.2016
Сообщений: 979
11.11.2019, 17:25 25
Enifan,
Цитата Сообщение от Enifan Посмотреть сообщение
Уверяю что данный пользователь сделал достаточное кол-во ошибок, ему еще самому есть что поучить
да) у всех есть ошибки.

Цитата Сообщение от Enifan Посмотреть сообщение
Главное чтобы он чему нибудь научился.
Думаю этого должно волновать, а не тебя)

Цитата Сообщение от Enifan Посмотреть сообщение
Лично я делая данное задание узнал что то новое для себя, возможно когда нибудь напишу качественную бинарную кучу с разными вариациями, доведя ее до ума.
зачем?)
0
1842 / 1184 / 501
Регистрация: 14.10.2018
Сообщений: 3,180
11.11.2019, 17:49 26
Цитата Сообщение от jester Посмотреть сообщение
Думаю этого должно волновать, а не тебя)
Когда учишь других - сам чему то учишься. Главное чтобы было чему учить.
Цитата Сообщение от jester Посмотреть сообщение
зачем?)
Самоудовлетворение. Люблю сложные задачи, типа Кольцевого-двусвязного-списка, много-функционального-консольного Морского боя с искусственным интеллектом и тд. Бинарную кучу понравилось делать, но пока не до неё.
0
Diamante
11.11.2019, 17:54
  #27

Не по теме:

Цитата Сообщение от Enifan Посмотреть сообщение
кучу понравилось делать
звучит!:D

0
Enifan
11.11.2019, 18:07
  #28

Не по теме:


Цитата Сообщение от Diamante Посмотреть сообщение
звучит!:D
Каждый испорчен в меру своей фантазии O_o . Интересно кто придумал такую терминологию, о чем он думал?

0
30 / 14 / 7
Регистрация: 08.01.2019
Сообщений: 636
13.11.2019, 11:06  [ТС] 29
Enifan,
Цитата Сообщение от Enifan Посмотреть сообщение
Vlast001, сам список работает не с даблом и строкой, а со структурой KeyValuePair
C#�������� ���
1
2
list.Add(value,data);
list.Add(new KeyValuePair(12.3, "string"));
Извините, но я так и не понял как. Ну то есть я делая как вы говорили, а оно все равно те же ошибки выдает(

В итого я решил сделать по другому. Но я от double отошел, так как когда я переделывал код просто под List<double>, ошибок не было, но в не которых моментах становиться совсем не понятно. Потому я пока, что с интом. Посмотрите пожалуйста, что я накалякал в файле Form1.cs
Кликните здесь для просмотра всего текста
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
using System;
using System.IO;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
 
namespace BHeap
{
    public partial class Form1 : Form
    {
        
        //Graphics pictGraphics;
        public Form1()
        {
            InitializeComponent();
            
        }
 
        private void Form1_Load(object sender, EventArgs e)
        {
            
        }
 
        private void ДейстивиеToolStripMenuItem_Click(object sender, EventArgs e)
        {
 
        }
 
        private void ПрочитатьИзФайлаToolStripMenuItem_Click(object sender, EventArgs e)
        {
            Stream  myStream;
            OpenFileDialog openFileDialog1 = new OpenFileDialog();
            openFileDialog1.InitialDirectory = "D:\\";
            openFileDialog1.Filter = "txt files (*.txt) |*.txt|All files (*.*) |*.*";
            openFileDialog1.FilterIndex = 2;
            openFileDialog1.RestoreDirectory = true;
            if (openFileDialog1.ShowDialog() == System.Windows.Forms.DialogResult.OK)
            {
                if ((myStream = openFileDialog1.OpenFile()) != null)
                {
                    MessageBox.Show("Read file was happend");
                    myStream.Close();
                }
            }
        }
        
        protected override void OnPaint(PaintEventArgs e)
        {
            base.OnPaint(e);
            Font drawFont = new Font("Arial", 5);
            SolidBrush drawBrush = new SolidBrush(Color.Black);
            StringFormat drawFormat = new StringFormat();
            drawFormat.FormatFlags = StringFormatFlags.DirectionRightToLeft;
 
            BinaryHeap binary = new BinaryHeap();
            Dictionary<int, string> dic = new Dictionary<int, string>();
            //dic.Add(binary.Add(900), "B1"); // не работает 
            //dic.Add(binary.Add(1100), "B2"); // не знаю как сделать, что бы работало
            dic.Add(1000, "B1");
            dic.Add(900, "B2");
           
            int x = 670, y = 30;
            int dx = 40;
            int deb = 1;
            
            foreach (string key in dic.Values)
            {
                //MessageBox.Show(key);
                e.Graphics.DrawEllipse(Pens.Red, x, y, 30, 30);
                e.Graphics.DrawString(key, drawFont, drawBrush, x, y, drawFormat);
                for (int i = 1; i <= 3; i++)
                {
                    for (int k = 0; k < deb; k++)
                    {
                        e.Graphics.DrawEllipse(Pens.Red, x - dx, y + 40, 30, 30);
                        e.Graphics.DrawEllipse(Pens.Red, x + dx, y + 40, 30, 30);
                        //e.Graphics.DrawLine(Pens.Black, x + 15, y+30, 255, 70);
                        //e.Graphics.DrawLine(Pens.Black, x + 15, y + 30, 455, 70);
                        dx += 40;
                    }
                    deb *= 2;
                    y += 40;
                }
            }
 
           
            
        }
    }
    class BinaryHeap
    {
        private List<int> list;
 
        public BinaryHeap()
        {
            list = new List<int>();
        }
 
        // Кол-во элементов в бинарной куче
        public int Count
        {
            get
            {
                return list.Count();
            }
        }
 
        // Добавление элемента
        public void Add(int value)
        {
            list.Add(value);
            if (Count == 1) // Всего один элемент,
                return;     // нечего перемещать
 
            // Получаем индексы текущего и родительского элементов
            int current = Count - 1;        // текущий (индекс в массиве начинается с нуля)
            int parent = (current - 1) / 2; // родитель (дробная часть у int отпадает)
 
            // Если нужно - перемещаем наибольший элемент наверх,
            // чтобы соотвествовать условию бинарной кучи
            while (list[parent] < list[current])
            {
                int temp = list[current];
                list[current] = list[parent];
                list[parent] = temp;
 
                // Получаем индексы текущего и родительского элементов
                current = parent;
                parent = (current - 1) / 2;
            }
        }
 
        // Удаление элемента
        public void Remove(int index)
        {
            if (index < 0 || index > Count - 1)
            {
                Console.WriteLine("Неверный индекс, удаление невозможно");
                return;
            }
            list[0] = list[Count - 1];
            list.RemoveAt(Count - 1);
            Heapify(0);
        }
 
        // Получение максимального элемента
        // true - не удалять элемент, false - удалить
        public int GetMax(bool check)
        {
            if (check == true)
                return list[0];
            int result = list[0];
            list[0] = list[Count - 1];
            list.RemoveAt(Count - 1);
            Heapify(0);
            return result;
        }
 
        // Проверить значение по текущему индексу,
        // не нарушает ли оно правило бинарной кучи
        void Heapify(int i)
        {
            int current;
            int leftChild;
            int rightChild;
 
            while (true)
            {
                current = i;
                leftChild = 2 * i + 1;
                rightChild = 2 * i + 2;
 
                // Проверка на выход за границы массива, и сравнивает значения
                if (leftChild < Count && list[leftChild] > list[current])
                {
                    current = leftChild;
                }
 
                // Проверка на выход за границы массива, и сравнивает значения
                if (rightChild < Count && list[rightChild] > list[current])
                {
                    current = rightChild;
                }
 
                // Значение находитсяна своем месте
                if (current == i)
                {
                    break;
                }
 
                int temp = list[i];
                list[i] = list[current];
                list[current] = temp;
                i = current;
            }
        }
 
        // Сортировка
        public void Sort()
        {
            list.Sort();    // Сортировка по возрастанию
            list.Reverse(); // Перевернуть все значения
        }
 
        // Глубина бинарной кучи
        public int Height()
        {
            return CounterHeight(Count);
        }
 
        // Подсчет глубины бинарной кучи
        int CounterHeight(int val)
        {
            if (val == 0) return 0;
            return (val / 2 > 0) ? CounterHeight(val / 2) + 1 : 1;
        }
 
        // Подсчет длины максимального значения
        int MaxLengthValue()
        {
            int maxLengthValue = 0;
            for (int i = 0; i < list.Count; i++)
            {
                if (maxLengthValue < list[i].ToString().Length)
                    maxLengthValue = list[i].ToString().Length;
            }
            return maxLengthValue;
        }
    }
}

В общем то, что я нарисовал это максимум, что я смог. Дальше нихрена не выходит, просто хз даже о чем думать идей ноль. Без понятие так же как мне рисовать эти DrowLine чтобы они только касались кружочков. Прикреплю вложение этого позора...хотя какой позор, я хз как это вообще делать чудом это "наугад" натыкал считая радиусы и т.д. Пытался найти какую-то формулу по который бы узлы рисовались в нужном расположении как во вложениях из первых постов.
Миниатюры
Как реализовать бинарную кучу (пирамиду)?  
0
1842 / 1184 / 501
Регистрация: 14.10.2018
Сообщений: 3,180
13.11.2019, 14:19 30
Vlast001, Примерный аналог прорисовки я делал в консоли, по сути перенести алгоритм оттуда сюда. Просто разберитесь как он работает.
0
30 / 14 / 7
Регистрация: 08.01.2019
Сообщений: 636
13.11.2019, 15:01  [ТС] 31
Цитата Сообщение от Enifan Посмотреть сообщение
по сути перенести алгоритм оттуда сюда. Просто разберитесь как он работает.
Как он работает я то разобрался, но я лично не вижу как просто взять и перенести туда алгоритм, сложно, очень сложно.
1. как изменить метод Add, чтобы его пропихнуть в словарь чтобы он заработал
2. Вот вы говорите просто разобраться и перенести. Давайте с самого начала
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
 protected override void OnPaint(PaintEventArgs e)
        {
            base.OnPaint(e);
            SolidBrush drawBrush = new SolidBrush(Color.Black);
            StringFormat drawFormat = new StringFormat();
            drawFormat.FormatFlags = StringFormatFlags.DirectionRightToLeft;
 
            BinaryHeap binary = new BinaryHeap();
            Dictionary<int, string> dic = new Dictionary<int, string>();
            dic.Add(binary.Add(1000), "B1"); //тут ошибки
            dic.Add(binary.Add(900), "B2"); // из-за того, что метод Add void
            int x = 670, y = 30;
            int dx = 40;
            int deb = 1;
            foreach (string key in dic.Values)
            {
                if (binary.Count == 0) // Нечего выводить на экран
                     return;
                if (binary.Count == 1) // Всего одно значение
                {
                       e.Graphics.DrawEllipse(Pens.Red, x, y, 30, 30);
                       e.Graphics.DrawString(key, drawFont, drawBrush, x + 20, y + 10, drawFormat);
                       return;
                }
            }        
        }
Так что-ли? Если да то, я кроме этого кусочка не пойму как перенести на форму остальное. Если не так, то я вообще не пойму что вы имели ввиду под перенести алгоритм, потому как за свои 3 месяца шарпа я лично не вижу никакого сходства формы с консолью
0
13.11.2019, 15:01
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.11.2019, 15:01
Помогаю со студенческими работами здесь

Нарисовать пирамиду из решеток похожую на пирамиду
Задача: нужно нарисовать пирамиду из решеток похожую на пирамиду , на которую взбирается Марио в...

Как написать бинарную константу
Здравствуйте. Как записать число в двоичном виде в переменную? Например: int i=10; //...

Как записать в файл бинарную матрицу
Имеется бинарная матрица созданная из ЛЧМ сигнала типа x_cos = chirp(tch_lf,f_begin,tch2,f_end); ...

про кучу и не кучу
уважаемые подскажите плиз, есть ли точный способ отличить по указателю, расположен объект в куче...


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

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

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