Down Heapify - Intro to Algorithms Udacity English Japanese

Down Heapify - Intro to AlgorithmsYouTube↗ IA↗(long shot)
Education 5.1K views 10 likes 1 dislikes 19 Jul 2012

Udacity 651K subscribers United States YouTube↗

Click to Play Video

Let's try to do this in a general way now. Right. So we call this procedure down heapify.

では一般的なやり方いわゆるheapify関数を試してみましょう

Let's talk about how we actually will go with this.

実際にどうやって作るのかを説明します

I've made a couple of helpful routines to help with the heap.

ヒープ操作のためのルーチンをいくつか作りました

given a position i in the heap, left (i) returns the position of the left child.

ヒープの中のある位置をiとし left(i)が左の子の位置を返します

Right (i )returns the position of the right child. Parent (i) returns the position of the parent.

right(i)は右の子の位置を parent(i)は親の位置を返します

Root (i) answers whether or not the node that we're talking about is a root.

root (i)は着目ノードがルートかどうかを答えます

There's no root. Leaf (L, i) returns whether or not we're looking at a leaf (i). In other words, it has no children.

leaf(L,i)はiがリーフかつまり子がないかどうかを答えます

It has no children if what where the right child would be is off the end of the list

右の子がリストの終わりにあれば iには子がありません

and where the left child would be is off the end of the list.

左の子がリストの終わりの場合も同様です

Then there's one other special kind of node and there can be at most one of these in the whole tree and that's a one_child node.

ツリー全体の中で特別なのが子が1個のノードです

That happens if a node has a left child, which is the very last element in the array.

もしノードに左の子があればそれが配列の終わりになります

The right child doesn't exist.

右の子はありません

That's just what I said that the right child is at the very end of the list

右の子がリストの最後でそこで終わっている場合も同様で

or off the end of the list then that's a one_child node.

そのノードは子が1個のノードです

Down heapify is this notion that we've got.

さらにdown_heapifyの概念を

We apply this in the notion where we've got a heap rooted at node i that satisfies

ノードiをルートとするヒープのプロパティを持つヒープに適用します

the heap property except perhaps i to its children, to its immediate children.

ただしiとそのすぐ下の子はヒープのプロパティを満たしていないようです

We can apply this if the heap property is satisfied.

ヒープのプロパティが満たされていれば適用できます

Everywhere except maybe between the root and its kids,

ただしルートとその子ノードは除きます

so the root in particular the node i and its kids.

この場合はルートであるノードiとその子のことです

Let's just say that. If i is actually a leaf, then we're done. Right.

iがリーフであればこれで終了です

We're satisfied everywhere except for between i and its children, and i doesn't have any children.

iとその子の間を除きヒープ条件が満たされ iは子がないからです

So, good. That's great. Heap property is restored.

これでヒープのプロパティが回復しました

If i has only one child, then we need to think a little harder.

ノードiに子が1個しかない場合は少し難しくなります

In the case where i has one child, we check the heap property between i and its one child on the left and if i is bigger than its child that's bad.

iに子が1個しかないケースではまず iと左にある子のヒープのプロパティをチェックしますもしiが子より大きければ残念ながら問題ありです

That means the heap property isn't satisfied but all we have to do to fix it is

ヒープのプロパティが満たされていないので修正します

we just swap the value in the left child and i.

ノードiとその子を置き換えます

That's what we did and then now we know that that last node

最後に置き換えたノードが

is the very last node in the tree and that node we just swapped into

ツリーの最後のノードだと分かっています

is the very last node in the tree so it must be that things are happy everywhere.

最後のノードを置き換えたのでこれですべてが満たされました

What if i has two children? So this is some internal node in the tree now. Or possibly a root of a large tree. So now we check the heap property. I'm going to do this this way. I'm going to ask look at the left and the right children, and look at the minimum value of those two.

子が2個のノードの場合ですツリーの内部のノードかルートでしょうヒープのプロパティを見ていきます手順はこうです左と右の子を比べてこの2つの最小値を求めます

If the minimum value is bigger than or equal to L[i] that means L[i]

もしその最小値がL[i]と等しいか大きい場合

the value at node i is smaller than both the kids so we're good.

L[i]つまりノードiの値が 2個の子ノードより小さいということで

The heap property is satisfied everywhere and we can just return.

ヒープのプロパティが満たされているので値を返します

On the other hand, sadly if that doesn't hold, then we need to see which child is the smallest

残念ながらそうでない場合 2つの子のどちらが最小値か

or the smaller of the two and swap i's value into that child.

2つを比べてiの値を小さい方の子と置き換えます

That's just what we're doing in the example by hand.

これが先ほど手でやった操作です

Let's check it. If the left child is smaller than the right child,

ではチェックしていきます左の子が右の子より小さければ

that means that the left child is the smallest one.

左の子が最小値です

We swap i and the left child's value and then we need to down heapify on the left child.

iと左の子を置き換えますそして左の子に沿ってdown_heapifyを進めます

We've basically fixed things everywhere except for possibly the tree rooted at left (i). It could actually not satisfy the heap property but that's okay.

left(i)をルートとするツリーの場合を除いて全部修正できました完全には修正できていないのですが大丈夫です

We can fix that by bubbling down the tree with down heapify once again.

down_heapifyを続けることで解決できます

It's just what we did when we're doing it by hand and then we can return.

これが先ほど手でやった操作ですこれで答えを返します

Finally, we reached this point, if the heap property is violated and the right child of i

このポイントでヒープのプロパティが満たされておらず

is between i and the right child of i so we can just swap i and the right child of i

左の子の値がiと右の子の間だった場合 iとその右側の子を置き換えます

possibly causing the tree rooted at the right child of i to be violated.

するとiの右の子をルートとするツリーがヒープのプロパティに違反するかもしれません

We just run down heapify starting from there. When that's done, we can return.

そこでここを始点にdown_heapifyを実行し終了すると値を返します

And we've established the heap property throughout the tree.

これでツリー全体のヒープが完成しました

Similar videos:

Top K Code - Intro to Algorithms
Udacity
722 views 2 likes 0 dislikes 19 Jul 2012100% match

ARE GETTING TATTOOS OKAY? | We Are The Davises
We Are The Davises
1.1M views 8.3K likes 566 dislikes 06 Apr 201758% match

Cómo desinfectar las tijeras de podar
nenavalente
2.3K views 53 likes 0 dislikes 07 Nov 201957% match

Crie um LED de Standby para seus equipamentos.
Eletrônica e Tecnologia
10.3K views 666 likes 8 dislikes 25 Dec 202056% match

МОРОЖЕНЩИК СХВАТИЛ КВАМИ! ЛЕДИБАГ и СУПЕР-КОТ должны повторить НЕВЕРОЯТНЫЕ ТРЮКИ из ТИК ТОК!
Watch Me
12.6M views 346.3K likes 27.4K dislikes 08 Feb 202056% match

Noah's Ghostbusters tricks! SuperHeroKids
SuperHeroKids
4.7M views 41.5K likes -1 dislikes 04 Jan 202056% match

Rocket To The Moon! Noah's Sneaky Joke on His Sisters! SuperHeroKids
SuperHeroKids
7.5M views 51K likes -1 dislikes 25 May 201956% match

OUR FUN FLOUR TOWER CHALLENGE
We Are The Davises
2.1M views 14.4K likes 674 dislikes 25 Jan 201756% match

Perches For High Flyer Pigeons
Maney Pigeons
17K views 554 likes 15 dislikes 11 Aug 202056% match

GIANT CHOCO PIE-NHƯ CHOCO PIE KHỔNG LỒ 50X-Tết Này Anh Không Về
Princess Bánh Bao
3.7M views 42.8K likes 4.1K dislikes 15 Dec 201756% match

How The Amazing Spider-Man Should Have Ended
How It Should Have Ended
21.5M views 192.7K likes 4.8K dislikes 27 Sep 201256% match

CHEAP A/C SLEEPER BUS IN INDIA - RISHIKESH TO DELHI
Travelling on a Shoestring
1.6K views 50 likes 4 dislikes 04 Aug 201956% match

【超小厨】3斤羊肉1斤羊排，麻辣羊排炖羊肉，全家辣的挤眉弄眼，吃饱打酱油，安逸！
ChefChao
260K views 5.5K likes 146 dislikes 13 Oct 202056% match

【SNOW MONKEY】☆Babies living in a harsh winter 02☆ ニホンザル / 地獄谷野猿公苑・志賀高原
 トックリ00 全映像記録集　~ by kiyo ~
6.1K views 0 likes 0 dislikes 19 Feb 202156% match

Acting Like A 'BABY' To See How My Korean Boyfriend Reacts *PRANK*
June Of Dasha
259.5K views 18.5K likes 251 dislikes 21 Aug 202055% match

1斤糍粑半斤辣，苗大姐先炸后炒，麻辣鲜香呼哧呼哧就是一大盘~【苗阿朵美食】
Miao Aduo cuisine
66K views 1.4K likes 69 dislikes 10 Nov 202055% match

Funniest Ever Stand Up Comedians On Got Talent
Got Talent Global
9.9M views 98.1K likes 3.1K dislikes 06 Jan 201655% match

Kapan kelinci menyusui bayinya ?
My Bunny
1.8K views 49 likes 2 dislikes 24 Nov 202055% match

भालू के बच्चे 8 भालू के बच्चे stories for Children हिंदी कार्टून hindi kahaniya
Moolt Hindi कार्टून
1.5M views 4K likes -1 dislikes 13 Jun 201755% match

Super Powers Go Crazy! Noah and Eden are out of control!
SuperHeroKids
10.6M views 63.8K likes -1 dislikes 12 Oct 201955% match

How Many Balls Can Kevin Hart and Anna Kendrick Absorb?
LOL! Network
15.6M views 96.3K likes -1 dislikes 08 Apr 201955% match

Ασκήσεις Για ΣΤΗΘΟΣ στο ΣΠΙΤΙ ΧΩΡΙΣ ΕΞΟΠΛΙΣΜΟ - Χτίσε Στήθος Με Παραλλαγές Κάμψεων
Leo Spartacus
2.3K views 148 likes 0 dislikes 07 Aug 202055% match

Lady Gaga - Alejandro Video Controversy
The Young Turks
6.5M views 3.8K likes 2.3K dislikes 10 Jun 201055% match

Prebeardy (Official Music Video)
nigahiga
6M views 214.7K likes 1.9K dislikes 12 Nov 201655% match

생후 1일된 신생아 아기와 보내는 첫 24시간 브이로그 국제커플 Our First 24 hours with a newborn baby AMWF
Young family영쀄밀리
65.1K views 2.8K likes 20 dislikes 06 Nov 202054% match

DANCING CHICKEN

2K views 193 likes 1 dislikes 03 Nov 202054% match

Массаж от инсульта и для пяти органов чувств. Му Юйчунь.
Zhen Gongfu
566.8K views 20.6K likes -1 dislikes 31 Jan 202154% match

【超小厨】直播唱嗨肚子饿，泡面+牛腩，做真正的牛肉方便面，夫妻俩深夜吃到爽！
ChefChao
211.6K views 5K likes 238 dislikes 01 Dec 202054% match

Hora de vender os Rhodes / Clube de canais / Ameraucanas
Granja Mascarenhas
40.4K views 2.7K likes 35 dislikes 04 Jan 202154% match

Bileklik Yapımı |Arkadaşlık Bilekliği Örme | Örgü Bileklik | Kumihimo Bileklik |friendshipbracelets
Sihirli ilmek sepeti - Amigurumi Örgü Tasarım
1.3K views 140 likes 0 dislikes 13 Oct 202054% match

Settings Privacy About Contact Donate