Что такое куча

В про­грам­ми­ро­ва­нии есть два раз­ных поня­тия, кото­рые обо­зна­ча­ют­ся одним и тем же сло­вом «куча». Одно про выде­ле­ние памя­ти, вто­рое — про орга­ни­за­цию дан­ных. Раз­бе­рём оба и закро­ем этот вопрос.

Это про данные

Эта ста­тья из цик­ла про типы дан­ных. Уже было: 

Ещё быва­ют свя­зан­ные спис­ки, оче­ре­ди, мно­же­ства, хеш-таблицы, кар­ты и кучи. Вот сего­дня про кучи. 

Куча и работа с памятью

Каж­дая запу­щен­ная про­грам­ма исполь­зу­ет соб­ствен­ную область опе­ра­тив­ной памя­ти. Эта область делит­ся на несколь­ко частей: в одной хра­нят­ся дан­ные, в дру­гой — сам код про­грам­мы, в тре­тьей — кон­стан­ты. Ещё в эту область вхо­дят стек вызо­вов и куча. Про стек вызо­вов мы уже рас­ска­зы­ва­ли в отдель­ной ста­тье, теперь пого­во­рим про кучу.

В отли­чие от сте­ка, кото­рый стро­го упо­ря­до­чен и все эле­мен­ты там идут друг за дру­гом, дан­ные в куче могут хра­нить­ся как угод­но. Тех­ни­че­ски куча — это область памя­ти, кото­рую ком­пью­тер выде­ля­ет про­грам­ме и гово­рит: вот тебе сво­бод­ная память для пере­мен­ных, делай с ней что хочешь. 

То, как про­грам­мист рас­по­ря­дит­ся этой памя­тью и каким обра­зом будет с ней рабо­тать, вли­я­ет на быст­ро­дей­ствие и рабо­то­спо­соб­ность всей про­грам­мы. 

Аналогия со стройплощадкой

Пред­ставь­те, что мы стро­им дом, а куча — это огром­ная пло­щад­ка для хра­не­ния строй­ма­те­ри­а­лов. Пло­щад­ка может быть боль­шой, но она не без­гра­нич­ная, поэто­му важ­но как-то по-умному ей поль­зо­вать­ся. Напри­мер: 

На строй­ке: мы выгру­зи­ли кир­пич на один уча­сток, исполь­зо­ва­ли этот кир­пич. Теперь нуж­но ска­зать, что этот уча­сток мож­но сно­ва исполь­зо­вать под строй­ма­те­ри­а­лы. Новый кир­пич мож­но раз­гру­зить сюда же, а не искать новое место на пло­щад­ке. 

В про­грам­ме: мы выде­ли­ли память для пере­мен­ной, исполь­зо­ва­ли пере­мен­ную, она боль­ше не нуж­на. Мож­но ска­зать «Эта память сво­бод­на» и исполь­зо­вать её сно­ва. 

На строй­ке: мы хра­ним опре­де­лён­ный вид труб на пале­те №53. Мы гово­рим кра­нов­щи­ку: «Под­ни­май­те на этаж то, что лежит на пале­те 53». Если мы оши­бём­ся с номе­ром, то кра­нов­щик под­ни­мет на этаж не те тру­бы. 

В про­грам­ме: в неко­то­рых язы­ках мы можем обра­тить­ся к куче напря­мую через спе­ци­аль­ный ука­за­тель. Если мы ошиб­лись и ска­за­ли обра­тить­ся не к тому участ­ку памя­ти, про­грам­ма забе­рёт не те дан­ные, а даль­ше будет ошиб­ка. 

👉 Пря­мой доступ к памя­ти есть не во всех язы­ках про­грам­ми­ро­ва­ния. Мно­гие ком­пи­ля­то­ры и интер­пре­та­то­ры ста­вят меж­ду про­грам­ми­стом и памя­тью свое­об­раз­но­го адми­ни­стра­то­ра — дис­пет­че­ра памя­ти. Он сам реша­ет, какие пере­мен­ные нуж­ны, а какие нет; когда чистить память; сколь­ко памя­ти на что выде­лить. 

С одной сто­ро­ны, это удоб­но: про­грам­мист про­сто гово­рит «хра­ни дан­ные». А где они будут хра­нить­ся и как их полу­чить — это вопрос дру­гой систе­мы. 

С дру­гой сто­ро­ны, авто­ма­ти­че­ские дис­пет­че­ры памя­ти быва­ют менее эффек­тив­ны­ми, чем если управ­лять памя­тью вруч­ную. Поэто­му драй­ве­ра или софт для высо­ко­на­гру­жен­ных систем чаще пишут в «руч­ном режи­ме». 

Куча и организация данных

Вто­рой вид кучи в про­грам­ми­ро­ва­нии — это орга­ни­за­ция дан­ных. 

Куча — это такой вид дере­ва, у кото­ро­го есть одно важ­ное свой­ство:

если узел A — это роди­тель узла B, то ключ узла A боль­ше клю­ча узла B (или равен ему).

Если мы пред­ста­вим какой-то набор дан­ных в виде кучи, он может выгля­деть, напри­мер, так:

Набор данных в виде кучи

У кучи нет огра­ни­че­ний на чис­ло потом­ков у каж­до­го роди­те­ля, но на прак­ти­ке чаще все­го исполь­зу­ют­ся бинар­ные кучи. Бинар­ные — зна­чит, у каж­до­го роди­те­ля может быть не боль­ше двух потом­ков.

Для чего нужны кучи данных

Так как дан­ные в куче упо­ря­до­че­ны зара­нее понят­ным обра­зом, то их мож­но исполь­зо­вать для быст­ро­го нахож­де­ния нуж­но­го эле­мен­та или опти­маль­ной после­до­ва­тель­но­сти дей­ствий, напри­мер:

  • для пира­ми­даль­ной сор­ти­ров­ки боль­шо­го коли­че­ства дан­ных, когда объ­ём тре­бу­е­мой памя­ти не зави­сит от раз­ме­ра мас­си­ва, кото­рый мы сор­ти­ру­ем;
  • для нахож­де­ния само­го быст­ро­го пути из точ­ки A в точ­ку B, когда мы зна­ем про­ме­жу­точ­ные рас­сто­я­ния меж­ду ними и точ­ка­ми по пути;
  • для поис­ка нуж­но­го эле­мен­та по каким-то кри­те­ри­ям за мини­маль­ное вре­мя;
  • для вычис­ле­ния опти­маль­ной после­до­ва­тель­но­сти дей­ствий, если мы зна­ем пара­мет­ры и усло­вия для каж­до­го дей­ствия.

Зачем это знать

Если вы про­сто пише­те веб-приложения на JS — в прин­ци­пе, это знать не нуж­но. Вы не може­те из JS напря­мую управ­лять памя­тью, а для про­стых задач вам вряд ли при­дёт­ся часто обхо­дить дере­вья и делать слож­ные сор­ти­ров­ки. 

Пони­ма­ние струк­тур дан­ных нуж­но для глу­бо­кой экс­перт­ной рабо­ты с соф­том. Это как пони­ма­ние прин­ци­пов рабо­ты меха­низ­ма внут­рен­не­го сго­ра­ния. Вам необя­за­тель­но в этом раз­би­рать­ся, если вы про­сто хоти­те водить авто­мо­биль, но обя­за­тель­но — если хоти­те соби­рать гоноч­ные боли­ды.

Текст и иллю­стра­ции:
Миша Поля­нин

Редак­тор:
Мак­сим Илья­хов

Кор­рек­тор:
Ира Михе­е­ва

Иллю­стра­тор:
Даня Бер­ков­ский

Вёрст­ка:
Маша Дро­но­ва

Достав­ка:
Олег Веш­кур­цев