Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Max Binary Heap Implement using Python
{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"class Heap(object):\n",
" \"\"\"Max Binary Heap\"\"\"\n",
" \n",
" def __init__(self, capacity=10):\n",
" self._default = object()\n",
" self.capacity = capacity\n",
" self.heap = [self._default] * self.capacity\n",
" \n",
" def __len__(self):\n",
" return len(self.heap) - self.heap.count(self._default)\n",
" \n",
" def __getitem__(self, i):\n",
" return self.heap[i]\n",
" \n",
" def insert(self, item):\n",
" \"\"\"O(1) + O(logN) time complexity\"\"\"\n",
" if self.capacity == len(self): # full\n",
" return\n",
" \n",
" self.heap[len(self)] = item\n",
" \n",
" self.fix_up(self.heap.index(item)) # check item's validation\n",
" \n",
" def fix_up(self, index):\n",
" \"\"\"\n",
" O(logN) time complexity\n",
" Violate:\n",
" 1. child value > parent value\n",
" \"\"\"\n",
" parent_index = (index-1)//2\n",
" if index > 0 and self.heap[index] > self.heap[parent_index]: \n",
" # swap\n",
" self.swap(index, parent_index)\n",
" self.fix_up(parent_index) # recursive\n",
" \n",
" def fix_down(self, index):\n",
" \"\"\"\n",
" O(logN) time complexity\n",
" Violate:\n",
" 1. child value > parent value\n",
" \"\"\"\n",
" parent = self.heap[index]\n",
" left_child_index = 2 * index + 1\n",
" right_child_index = 2 * index + 2\n",
" largest_index = index\n",
" \n",
" if left_child_index < len(self) and self.heap[left_child_index] > parent:\n",
" largest_index = left_child_index\n",
" \n",
" if right_child_index < len(self) and self.heap[right_child_index] > self.heap[largest_index]: \n",
" largest_index = right_child_index\n",
" \n",
" if index != largest_index:\n",
" self.swap(index, largest_index)\n",
" self.fix_down(largest_index) # recursive\n",
" \n",
" def heap_sort(self):\n",
" \"\"\"\n",
" O(NlogN) time complixity\n",
" \"\"\"\n",
" for i in range(0, len(self)):\n",
" self.poll() \n",
" \n",
" def swap(self, i1, i2):\n",
" self.heap[i1], self.heap[i2] = self.heap[i2], self.heap[i1]\n",
" \n",
" def poll(self):\n",
" max_ = self.max_\n",
" \n",
" self.swap(0, len(self) - 1) # swap first and last\n",
" self.heap[len(self) - 1] = self._default\n",
" self.fix_down(0)\n",
" \n",
" return max_\n",
" \n",
" @property\n",
" def max_(self):\n",
" return self.heap[0]"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"h = Heap()\n",
"h.insert(10)\n",
"h.insert(5)\n",
"h.insert(30)\n",
"h.insert(15)\n",
"h.insert(1)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"30\n",
"15\n",
"10\n",
"5\n",
"1\n",
"<object object at 0x7f121b0bc480>\n",
"<object object at 0x7f121b0bc480>\n",
"<object object at 0x7f121b0bc480>\n",
"<object object at 0x7f121b0bc480>\n",
"<object object at 0x7f121b0bc480>\n"
]
}
],
"source": [
"for i in h:\n",
" print(i)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"30"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"h.poll()"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"15\n",
"5\n",
"10\n",
"1\n",
"<object object at 0x7f121b0bc480>\n",
"<object object at 0x7f121b0bc480>\n",
"<object object at 0x7f121b0bc480>\n",
"<object object at 0x7f121b0bc480>\n",
"<object object at 0x7f121b0bc480>\n",
"<object object at 0x7f121b0bc480>\n"
]
}
],
"source": [
"for i in h:\n",
" print(i)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.5.2"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment