• #### 科普

SCIENCE

#### 英语

ENGLISH

#### 科技

TECHNOLOGY

MOVIE

FOOD

#### 励志

INSPIRATIONS

#### 社会

SOCIETY

TRAVEL

#### 动物

ANIMALS

KIDS

#### 卡通

CARTOON

#### 计算机

COMPUTER

#### 心理

PSYCHOLOGY

#### 教育

EDUCATION

#### 手工

HANDCRAFTS

#### 趣闻

MYSTERIES

CAREER

GEEKS

#### 时尚

FASHION

• 精品课
• 公开课
• 欢迎下载我们在各应用市场备受好评的APP

点击下载Android最新版本

点击下载iOS最新版本

扫码下载译学馆APP

#### 数据结构：堆

Data Structures: Heaps

Hi, I’m Gayle Laakmann McDowell, author of Cracking the Coding Interview. Today we’ll talk

about a topic that a lot of candidates forget about, heaps. Heaps come in one of

two forms, a min heap or max heap. We’ll just focus on min heaps today because a

max heap is essentially the reverse. In a min heap the elements are all smaller than

their children so the root node will be the very smallest element and then

looking down the tree down the heap, the elements get bigger and bigger and

bigger.

So that’s the basics of what a heap is but how do we actually create and maintain

such a data structure? So let’s start with just insertion. So when we insert an

element it always goes in the next empty spot looking top to bottom left to right.

So we go, first we insert an element here, and then here and then here and then

here and so on through the tree, through the heap. So that’s how insertion works.

But then of course what happens if that’s not really where the element

should go?

What we can do is we can insert the element there and then bubble it up

until we get to the right spot. So we take the inserted element, we compare it

with its parent, if it’s out of order, swap them and then keep going up the

tree in this process. Now what about removing the minimum element? So

we know the minimum element will always be the root node and so that’s easy to

find but then if we want to remove it we might have an empty spot. So what we

do here is we remove the min element there, so we take out the root and then

we swap that value at the root with the last element added. And then of course

that element might not be in the right spot, so we take the root element and bubble

it down to the next spot so we compare the root with its children, its left

child and its right child, and then swap it with the smaller of the two. And then we

keep going down the tree until the heap property is restored. So that’s how a

tree operates, let’s think about implement- that’s how a heap operates, let’s talk

about implementation now. So implementation is kind of interesting.

You might have assumed that we’d implement it a simple class node with a

left node and a right node, and certainly we could do it that way. But

there’s an even better way of implementing it.

Note that when we add elements to the heap they’re always getting added in a

very particular spot. There aren’t gonna be any gaps in the heap so we have the

zeroth element here and then the first second third fourth etc and so that

means that we can actually use an array instead to store these values and

that makes it very compact. And a simple simple equation can map from an index to

its left child its right child or to its parent. And so we can still get to

the left and right child but we don’t need to have this overhead of a node

class. So now that we’ve covered the basics of what a heap is let’s turn to

the actual code for this. We’ll implement min heap with a simple class that wraps

this items array. This is going to be an array of a fixed length but if it

gets too big we’ll increase the capacity. Now I’m gonna get a little bit of a head

start and cheat a little bit by just adding a whole bunch of simple

helper methods. So these are just simple methods that get the left and right

child of the parent index. Actually you know check if they exist, or

actually get the values themselves. So I’m just getting a little bit of a head

start here and I’ll get another little bit of a head start by adding in two extra

methods here. One is a swap method that swaps the values of two indices and

another one is an insure extra capacity method. Now what this does is it checks if the

array is full and if so, it creates a new array of double that size and it copies

all the elements over. And this by the way is the basics of how an arraylist

operates. Now let’s turn to the real code. The first method I’ll implement

is a peek method and this

first checks if the array is empty if so returns an exception because there’s nothing

at the front. Otherwise it just returns the first element in the array which

will always be the minimum element, and essentially the root of the heap. The next method we’ll

do is a poll method. Now what this does is actually extract the minimum element

and actually so actually removes it from the array. So first we’ll check if the arrays

empty, if so throw an exception.

Otherwise I need to actually get the value so item is item of 0 then I need to

take the very last element in the array and move it into the very first element

then I need to shrink my array.

Or shrink essentiall the size of it. And then I need to go and actually re-heapify.

So I removed the root element so I need to heapify down and I’ll go fill

this in, this method in shortly.

So in this case if we remove the ten, the minimum element, it’s going to get

deleted. Then the 17 is going to get moved up to where the ten is, so seeing

the array, that’s like this,

the 17 gets put in here. And then we go and adjust the heap to shift elements

down as needed.

My next method is going to actually add an element in here. So first thing I want

to do is I wanna make sure there is capacity, so I’ll call my insure

extra capacity method. Then I’m gonna add my element into the very last spot so

items of size equals this new item then increase my size. And then I need to

actually heapify up so I need to fix the heap looking upwards. Swapping

each element with its parent as necessary, so in this case if we want to

add an element say, 8, we’d add it at the very last element and then we’d go and

adjust our heap moving things up as necessary.

Now for the real fun. I need to actually implement these heapify methods so

size minus 1 and then it’s going to walk up as long as there’s a parent item and

as long as essentially I’m out of order. So as long as my parent item is bigger

than me then hey, things are out of order, so swap my parent index, swap my value

with my parent and then walk upwards.

So let’s walk through this on the 8 that was inserted. So what we do here is

we’ll compare 8 to this 15, it’s out of order so we’ll need to swap those values.
15向下 8向上 在数组里就是这样
So 15 goes down here and 8 goes up here or on the array it will look like this. Then

we compare this 8 to the 10 and then that’s still out of order, and so we’ll go

and move the 10 down and swap the 8 up there and now we’ve returned to the

root, to the heap properties. We have 8 at the top, 10 and 20 below it then 17

and 15 below that. Heapify down is a little bit more complicated but it’s

still quite manageable. First we’re going to start off with our root element which

is at index zero. And then we’re going to say well as long as I have children, keep

walking down and trying to fix up my heap.

Now I only need to check if there’s a left child because if there’s no left

child then there’s certainly no right child. Then I’m gonna set this smaller

child index equal to the smaller of the left and the right child so I’m going to

take it guess with, set it equal to the left child, and then I’m gonna say hey if

there’s a right child,

and my right child is even smaller than my left child, small child index should

equal my right child. Now what I’m going to say,

remember I’m looking downwards on the heap, so now what I’m gonna say is hey, if items of

index, if I’m smaller than the smaller of my two children then everything’s good,

and everything’s back in order here and I can just exit.

If that’s not the case then our heap is still out of order and then I need to

swap my value with my smaller child and then move down to my smaller child. I’ll

just actually move this out here.

Alright so that’s the basics of how heapify down works. Let’s walk through

this on an example. I’ll make this example slightly larger so if we do an extract

min such that 20, 10 gets removed then we remove 10, we replace it with 25. I’ll do

it on the array too so you can see what’s going on there. Then we compare 25, the

root, and replace it with the smaller of its left and right child. So we swap the

25 and the 15, so 25 comes down here, 15 comes up there, and we can do it down

here too. So 15 goes here 25 goes here then we compare 25 to 17. It’s still out of

order since 25 is bigger than 17 so we do 17 comes up here we swap

those and 25 goes down here. So now we have a heap again that looks like 15, 17
17 20 然后25 最小堆的性质就满足了
20, and 25 and as you can see our min heap property has been restored. So now

that you understand what a heap is and how it works,

why don’t you try out using a heap on a new problem. Good luck.

[B]刀子