Бинарная куча с использованием указателей

@abylkasymov · Регистрация: 12.12.2016

Студворк — интернет-сервис помощи студентам

Доброе время суток, форумчане. В качестве домашней работы было задано построить бинарную кучу с использованием массивов. Но за кучу с указателями был обещан бонус-балл, такие дела. Так вот хотелось бы показать, как я попробовал сделать, и узнать о возможных (в моем случае тем более) ошибках

Java
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
import java.util.Stack;
 
public class HeapTree{
    class Node{
        Node left, right, parent;
        int value;
        int index;
        public Node(int value){
            this.value = value;
        }
        public Node(){}
    }
    Node head;
    Node last;
    int size;
 
 
    public HeapTree()
    {
 
        head = null;
        last = null;
    }
    public static String toBinary(int int1){
        return (Integer.toBinaryString(int1));
    }
    public void insert( int value){
        if ( head == null)
        {
            head = new Node(value);
            head.left = null;
            head.right = null;
            head.parent = null;
            size++;
            return;
        }
        Node temp = head;
        String word = toBinary(size+1);
        for ( int i =1; i < word.length(); i++)
        {
            if (temp.right == null || temp.left == null)
            {
                if(word.charAt(i)=='0'){
                    temp.left = new Node(value);
                    temp.left.parent = temp;
                    bubbleUp(temp.left);
                }
                else {
                    temp.right = new Node(value);
                    temp.right.parent = temp;
                    bubbleUp(temp.right);
                }
                size++;
                return;
            }
            if(word.charAt(i)=='0'){
                temp = temp.left;
            }
            else temp = temp.right;
        }}
 
 
    public Node findNode(int number){
        Node temp = head;
        String word = toBinary(number);
        for ( int i =1; i < word.length(); i++)
        {
            if(word.charAt(i)=='0'){
                temp = temp.left;
            }
            else temp = temp.right;
        }
        return temp;
    }
    public void print(Node head)
    {
        Node temp = head;
        if (temp!=null)
        {
            System.out.println(temp.value);
            print(temp.parent);
        }
    }
    public void bubbleUp(Node head)
    {
        Node temp = head;
        while (temp.parent!=null)
        {
            if (temp.value >= temp.parent.value)
            {
                return;
            }
            if ( temp.value < temp.parent.value){
                swap(temp, temp.parent);
            }
            temp = temp.parent;
        }
    }
 
    public void swap(Node temp, Node parent) {
        int tempNum = temp.value;
        temp.value = parent.value;
        parent.value = tempNum;
    }
    public void deleteMin(){
 
        Node temp = findNode(this.size);
        head.value = temp.value;
 
        if(this.size%2==1)
            {
                temp.parent.right = null;
            }
        else
            {
            temp.parent.left = null;
            }
        sinkDown();
        size--;
    }
    public void sinkDown(){
        Node temp = head;
        while(true){
            if(temp.left == null){
                return;
            }
            else if (temp.right == null){
                if (temp.value > temp.left.value)
                swap(temp, temp.left);
                return;
            }
 
 
            if (temp.value <= temp.right.value && temp.value <=temp.left.value ) return;
 
            if (temp.left.value < temp.right.value)
            {
                swap(temp, temp.left);
                temp = temp.left;
            }
            else {swap(temp, temp.right); temp = temp.right;}
 
        }
 
        }
 
 
    public static void main ( String args[])
    {
        HeapTree heapTree = new HeapTree();
        heapTree.insert(35);
        heapTree.insert(33);
        heapTree.insert(42);
        heapTree.insert(11);
        heapTree.insert(52);
        heapTree.insert(22);
        heapTree.insert(66);
       
        System.out.println(heapTree.head.value);
        System.out.println(heapTree.head.left.value);
        System.out.println(heapTree.head.right.value);
        System.out.println(heapTree.head.left.left.value);
        System.out.println(heapTree.head.left.right.value);
        System.out.println(heapTree.head.right.left.value);
        System.out.println(heapTree.head.right.right.value);
 
 
    }}

@KEKCoGEN · 02.10.2017, 08:56

Сообщение от abylkasymov

Но за кучу с указателями был обещан бонус-балл

жаль что в джава указателей нет, так что бонус балла можете не ждать)

@woldemas · 02.10.2017, 09:54

abylkasymov, вообще-то неразумно для кучи использовать дерево, она в обычном массиве хранится должна

@xoraxax · 02.10.2017, 10:35

Сообщение от woldemas

abylkasymov, вообще-то неразумно для кучи использовать дерево, она в обычном массиве хранится должна

обоснуй

@woldemas · 02.10.2017, 10:41

Сообщение от xoraxax

обоснуй

Удобная структура данных для сортирующего дерева — массив A, у которого первый элемент, A[1] — элемент в корне, а потомками элемента A[i] являются A[2i] и A[2i+1] (при нумерации элементов с первого). При нумерации элементов с нулевого, корневой элемент — A[0], а потомки элемента A[i] — A[2i+1] и A[2i+2].

Взято отсюда: https://ru.wikipedia.org/wiki/... 1%87%D0%B0

@abylkasymov · 02.10.2017, 16:07 **[ТС]**

Да, Вы правы, но все же обьекты в Java могут быть использованы как указатели, так как у них тип reference, насколько я знаю. И как в с++ можно написать

C++
1
2
3
4
 struct Node {
 Node*left;
 Node *right;
 int value;}

в Java можно создать класс

Java
1
2
3
4
 
class Node{
 Node right, left;
 int value;}

@Kukstyler · 02.10.2017, 16:26

Сообщение от abylkasymov

обьекты в Java могут быть использованы как указатели

Java работает только by reference, то есть по адресам. Но в Java нет понятия указателя (мы не можем напрямую работать с памятью), а есть понятие ссылки (т.к. by reference). Ссылка - это (технически) указатель, но константный.

Думаю, для здорового мышления в Java, лучше забыть про указатели, как таковые.

Новые блоги и статьи Все статьи Все блоги /
Функция установки текстового статуса в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем
10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .

Бинарная куча с использованием указателей

Решение

Решение

@woldemas 677 / 479 / 216 Регистрация: 06.09.2013 Сообщений: 1,312
	02.10.2017, 09:54
	abylkasymov, вообще-то неразумно для кучи использовать дерево, она в обычном массиве хранится должна 0