4 added 10 characters in body

# META:

As a few people just pointed out, if you sort the list, this also produces a correct heap. I'm now trying to come up with a more interesting application of heaps.

Given a list of integers, heapify this list and return it. The sumission must have a worst case time complexity in O(n).

### Details

• Your implementation can produce min- or max-heaps, whatever is more convenient.
• Sorting the list would solve the problem, but since the worst case complexity must be in O(n) where n is the length of the list, most known sorting algorithms like quicksort fail to meedmeet this requirement.

### Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k


For a max heap we just replace >= with <=.

### Examples

Following image represents a max heap: The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]


The following image represents a min heap: The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]


# META:

As a few people just pointed out, if you sort the list, this also produces a correct heap. I'm now trying to come up with a more interesting application of heaps.

Given a list of integers, heapify this list and return it. The sumission must have a worst case time complexity in O(n).

### Details

• Your implementation can produce min- or max-heaps, whatever is more convenient.
• Sorting the list would solve the problem, but since the worst case complexity must be in O(n) where n is the length of the list, most known sorting algorithms fail to meed this requirement.

### Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k


For a max heap we just replace >= with <=.

### Examples

Following image represents a max heap: The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]


The following image represents a min heap: The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]


# META:

As a few people just pointed out, if you sort the list, this also produces a correct heap. I'm now trying to come up with a more interesting application of heaps.

Given a list of integers, heapify this list and return it. The sumission must have a worst case time complexity in O(n).

### Details

• Your implementation can produce min- or max-heaps, whatever is more convenient.
• Sorting the list would solve the problem, but since the worst case complexity must be in O(n) where n is the length of the list, known sorting algorithms like quicksort fail to meet this requirement.

### Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k


For a max heap we just replace >= with <=.

### Examples

Following image represents a max heap: The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]


The following image represents a min heap: The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]

3 added 64 characters in body

# META:

As a few people just pointed out, if you sort the list, this also produces a correct heap. I'm now trying to come up with a more interesting application of heaps.

Given a list of integers, heapify this list and return it. The sumission must have a worst case time complexity in O(n).

### Details

• Your implementation can produce min- or max-heaps, whatever is more convenient.
• Sorting the list would solve the problem, but since the worst case complexity must be in O(n) where n is the length of the list, most known sorting algorithms fail to meed this requirement.

### Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k


For a max heap we just replace >= with <=.

### Examples

Following image represents a max heap: The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]


The following image represents a min heap: The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]


# META:

As a few people just pointed out, if you sort the list, this also produces a correct heap. I'm now trying to come up with a more interesting application of heaps.

Given a list of integers, heapify this list and return it.

### Details

• Your implementation can produce min- or max-heaps, whatever is more convenient.

### Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k


For a max heap we just replace >= with <=.

### Examples

Following image represents a max heap: The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]


The following image represents a min heap: The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]


# META:

As a few people just pointed out, if you sort the list, this also produces a correct heap. I'm now trying to come up with a more interesting application of heaps.

Given a list of integers, heapify this list and return it. The sumission must have a worst case time complexity in O(n).

### Details

• Your implementation can produce min- or max-heaps, whatever is more convenient.
• Sorting the list would solve the problem, but since the worst case complexity must be in O(n) where n is the length of the list, most known sorting algorithms fail to meed this requirement.

### Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k


For a max heap we just replace >= with <=.

### Examples

Following image represents a max heap: The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]


The following image represents a min heap: The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]

2 added 176 characters in body

# META:

As a few people just pointed out, if you sort the list, this also produces a correct heap. I'm now trying to come up with a more interesting application of heaps.

Given a list of integers, heapify this list and return it.

### Details

• Your implementation can produce min- or max-heaps, whatever is more convenient.

### Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k


For a max heap we just replace >= with <=.

### Examples

Following image represents a max heap: The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]


The following image represents a min heap: The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]


# Heapify a list

Given a list of integers, heapify this list and return it.

### Details

• Your implementation can produce min- or max-heaps, whatever is more convenient.

### Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k


For a max heap we just replace >= with <=.

### Examples

Following image represents a max heap: The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]


The following image represents a min heap: The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]


# META:

As a few people just pointed out, if you sort the list, this also produces a correct heap. I'm now trying to come up with a more interesting application of heaps.

Given a list of integers, heapify this list and return it.

### Details

• Your implementation can produce min- or max-heaps, whatever is more convenient.

### Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k


For a max heap we just replace >= with <=.

### Examples

Following image represents a max heap: The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]


The following image represents a min heap: The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]

1