heap structure

Introduction

日本語 ver

Today, I will write about heap structure. The heap structure is one of the data structure. My reason of studying heap structure is that I joined seminar of Ritsumeikan Univ.
I used this slide in seminar of Ritsumeikan Univ.


Overview

• data structure
• binary tree
• heap
• Implementation
• heap sort

Data structure

I will explain about data structure before explaining about heap.

Data structure is how to keep data. Data structure is selected on the basis of operation which you want to. 

Heap belong to data structure called priority queue. priority queue have purpose which 

1. add data
2. pick up minimum data (and remove) 

Binary Tree
Let, E and V are sets. The element $e \in E$ is called edge. The element $v \in V$ is called node.
g:E->V×V is map to V × V from E.
(E,V,g) is called graph.

For example,

The arrows are edge. The circles are node. This is expressed map. It is possible to go to node 3 from 1.

Rooted tree is tree as follows.

The node is spread from node 1.

Specially, binary tree is as follows.

Characteristic of this graph is separated to two node and node clogged from above and left side.
Top node of this graph is called root.
For example, node 1 is called parent of node 2. The node 4 and node 5 is children of node 2. node 8,9,10,11,12 is called leaf.

Heap
The heap structure is data structure expressed priority queue by using binary tree.

The priority queue want to 

1. add data
2. pick up minimum data (and remove) 

.

Firstly, adding data to heap structure.
1. attach new data in last node of graph.

2. next, if c is younger than D, D is replaced by C.

3. repeat 2 until that parent of C which younger than C is not exists.

Secondly, Picking up minimum data.
1. pick up A

2. copy last node to root.

 3. remove last node E

4. Swap E and child node B or D if child node is younger than E. If all child is younger than E, swap E and minimum child.

this method is needfully for keeping heap structure.

Implementation
When you implement heap structure, use array or list.
The number of child node is 2 times parent node number + 1 or 2 times parent node number +2. The 2 times parent node number + 1 is left child. The 2 times parent node number + 2 is right child.

This gif is value of array of heap structure. I add 10 data and pick up 10 data.

Heap sort
heap sort is sort method by using heap structure. The random array sorted by adding and picking heap structure.

This gif is value of array. The value picked up from heap structure.


Reference
https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E3%83%81%E3%83%A3%E3%83%AC%E3%83%B3%E3%82%B8%E3%83%96%E3%83%83%E3%82%AF-%E7%AC%AC2%E7%89%88-%EF%BD%9E%E5%95%8F%E9%A1%8C%E8%A7%A3%E6%B1%BA%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E6%B4%BB%E7%94%A8%E5%8A%9B%E3%81%A8%E3%82%B3%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0%E3%83%86%E3%82%AF%E3%83%8B%E3%83%83%E3%82%AF%E3%82%92%E9%8D%9B%E3%81%88%E3%82%8B%EF%BD%9E-%E7%A7%8B%E8%91%89%E6%8B%93%E5%93%89/dp/4839941068