{"id":1076,"date":"2010-06-21T15:41:50","date_gmt":"2010-06-21T15:41:50","guid":{"rendered":"http:\/\/www.codingfriends.com\/?p=1076"},"modified":"2011-01-14T13:36:20","modified_gmt":"2011-01-14T13:36:20","slug":"priority-queues","status":"publish","type":"post","link":"https:\/\/www.codingfriends.com\/index.php\/2010\/06\/21\/priority-queues\/","title":{"rendered":"Priority queues"},"content":{"rendered":"

<\/a><\/span>This is all about priority queue problems with using different techniques for storing the data in a queue, the priority queue could be similar to a queue in a hospital ER ward where the people with the biggest of problems are treated first. I am finding all of the computer science course at Stanford really interesting.<\/p>\n

But a heap implementation is similar to a binary tree<\/a> where the top node is the lowest value and the further you go down each part of the tree you will find higher and higher values. As you can see the below picture, but the main thing is that the highest values may be associated on another place compared to the next highest value, but when you remove the minimum value then you place the last node from the tree to the top node and then move that down to where it should be.<\/p>\n

\"Heap<\/a>
CS106B Assignment 4 Part 2<\/figcaption><\/figure>\n

So to insert the values, I am using a recursive funciton<\/p>\n

\r\nvoid PQueue::insertValue(int heapInsert)\r\n{\r\n\tint newElemI = heapInsert;\r\n\t\/\/ need to find out if the parent value\r\n\tif (heapInsert > 0)\r\n\t{\r\n\t\t\/\/ decrement the heapInsert since we start from 0.\r\n\t\theapInsert--;\r\n\t\t\/\/ if we are at the top then make it check with the top\r\n\t\tif (heapInsert == 1) \r\n\t\t\theapInsert=0; \r\n\t\telse \/\/ else goto the parent node\r\n\t\t\theapInsert\/=2;\r\n\t\t\/\/ if parent node is greater than the present node, then swap and go up\r\n\t\tif (heapValues[(heapInsert)] > heapValues[newElemI])\r\n\t\t{\r\n\t\t\t\/\/ swap values\r\n\t\t\tswapValues((heapInsert), newElemI);\r\n\t\t\treturn insertValue(heapInsert);\r\n\t\t}\r\n\t}\r\n\treturn;\r\n}<\/pre>\n
where it will call itself if a swap happens e.g the parent node is higher in value than the present node that we are checking, and the way that it works out the parent node is to divide the heapInsert by 2, but of course the top 3 nodes that is a special condition and also since arrays start from 0, then we have to — (-1) from the heapinsert value to start with.  The newElemI is where we are at present.<\/p>\n
To remove the top element, we need to remove that element and replace with the last node from the array, but then move this value down into the tree depending on if the value is less higher than the lowest value beneath it, so once again I did a recursive method that will call itself if a swap occurs, we just need to test the lower left\/right elements first to find the lowest value and then check against that with the parent value and if so, swap.<\/p>\n
\r\nvoid PQueue::moveRootDown(int rootID)\r\n{\r\n\t\/\/ test to see which one of the lower two are the smallest of values\r\n\tint leftValue = (rootID*2);\r\n\tint rightValue = (rootID*2)+1;\r\n\tint smallest =-1;\r\n\tif (leftValue <= heapUsedSize)\r\n\t\tsmallest = leftValue;\r\n\tif (rightValue <= heapUsedSize)\r\n\t\tif (heapValues[smallest-1] > heapValues[rightValue-1])\r\n\t\t\tsmallest = rightValue;\r\n\tif (smallest == -1) return;\r\n\tif (heapValues[rootID-1] > heapValues[smallest-1])\r\n\t{\r\n\t\tswapValues(rootID-1, smallest-1);\r\n\t\tmoveRootDown(smallest);\r\n\t}\r\n}<\/pre>\n
that was the main aspects again of the assignment and here is the full source code, I have included the source code and the assignment PDF file in the zip file attached<\/p>\n
\r\n#include \"pqueue.h\"\r\n#include \"genlib.h\"\r\n#include \r\n\r\n\/* \r\nheap implementation\r\n*\/\r\n\r\nconst int heapStart = 10;\r\n\r\nPQueue::PQueue()\r\n{\r\n\theapSize = heapStart;\r\n\theapValues = new int[heapStart];\r\n\theapUsedSize = 0;\r\n}\r\n\r\nPQueue::~PQueue()\r\n{\r\n\tdelete[] heapValues;\r\n}\r\n\r\nbool PQueue::isEmpty()\r\n{\r\n\tif (heapUsedSize == 0)\r\n\t\treturn true;\r\n\telse\r\n\t\treturn false;\r\n}\r\n\r\nint PQueue::size()\r\n{\r\n\treturn heapUsedSize;\r\n}\r\n\r\nvoid PQueue::add(int newElem)\r\n{\r\n\t\/\/ if we are the max then double\r\n\tif (heapSize == heapUsedSize)\r\n\t\tdoubleCapacity();\r\n\theapValues[heapUsedSize] = newElem;\r\n\tinsertValue(heapUsedSize);\r\n\theapUsedSize++;\r\n}\r\n\r\n\/\/ newElemI = index value of the new insert\r\nvoid PQueue::insertValue(int heapInsert)\r\n{\r\n\tint newElemI = heapInsert;\r\n\t\/\/ need to find out if the parent value\r\n\tif (heapInsert > 0)\r\n\t{\r\n\t\t\/\/ decrement the heapInsert since we start from 0.\r\n\t\theapInsert--;\r\n\t\t\/\/ if we are at the top then make it check with the top\r\n\t\tif (heapInsert == 1) \r\n\t\t\theapInsert=0; \r\n\t\telse \/\/ else goto the parent node\r\n\t\t\theapInsert\/=2;\r\n\t\t\/\/ if parent node is greater than the present node, then swap and go up\r\n\t\tif (heapValues[(heapInsert)] > heapValues[newElemI])\r\n\t\t{\r\n\t\t\t\/\/ swap values\r\n\t\t\tswapValues((heapInsert), newElemI);\r\n\t\t\treturn insertValue(heapInsert);\r\n\t\t}\r\n\t}\r\n\treturn;\r\n}\r\n\r\nvoid PQueue::swapValues(int swap1, int swap2)\r\n{\r\n\tint tmp = heapValues[swap1];\r\n\theapValues[swap1] = heapValues[swap2];\r\n\theapValues[swap2] = tmp;\r\n}\r\n\r\nvoid PQueue::printOut()\r\n{\r\n\tfor (int i =0; i < heapUsedSize; i++)\r\n\t\tcout << \"i \" << i  << \"   \" << heapValues[i] << endl;\r\n}\r\n\r\n\/\/ double the capacity of the heap size\r\nvoid PQueue::doubleCapacity()\r\n{\r\n\tint *temp = new int[heapSize*2];\r\n\tfor (int i =0; i < heapSize; i++)\r\n\t\ttemp[i] = heapValues[i];\r\n\tdelete[] heapValues;\r\n\theapValues = temp;\r\n\theapSize *=2;\r\n}\r\n\r\nint PQueue::extractMin()\r\n{\r\n\tif (isEmpty())\r\n\t\tError(\"no more values\");\r\n\telse\r\n\t{\r\n\t\tint returnValue = heapValues[0];\r\n\t\theapUsedSize--;\r\n\t\theapValues[0] = heapValues[heapUsedSize];\r\n\t\tmoveRootDown(1);\r\n\t\treturn returnValue;\r\n\t}\r\n\treturn 0;\r\n}\r\n\r\nvoid PQueue::moveRootDown(int rootID)\r\n{\r\n\t\/\/ test to see which one of the lower two are the smallest of values\r\n\tint leftValue = (rootID*2);\r\n\tint rightValue = (rootID*2)+1;\r\n\tint smallest =-1;\r\n\tif (leftValue <= heapUsedSize)\r\n\t\tsmallest = leftValue;\r\n\tif (rightValue <= heapUsedSize)\r\n\t\tif (heapValues[smallest-1] > heapValues[rightValue-1])\r\n\t\t\tsmallest = rightValue;\r\n\tif (smallest == -1) return;\r\n\tif (heapValues[rootID-1] > heapValues[smallest-1])\r\n\t{\r\n\t\tswapValues(rootID-1, smallest-1);\r\n\t\tmoveRootDown(smallest);\r\n\t}\r\n}<\/pre>\n
here is what I added to the header file for the private aspects of the class.<\/p>\n
\r\n    \/\/ heap size = the total amount of size \r\n    \/\/ heap used size = the amount of used space in the heap size\r\n    \/\/ heap values = the actual values within the heap\r\n    int heapSize, heapUsedSize;\r\n    int *heapValues;\r\n\r\n    void doubleCapacity();\r\n\tvoid printOut();\r\n\tvoid insertValue(int heapInsert);\r\n\tvoid swapValues(int swap1, int swap2);\r\n\tvoid moveRootDown(int rootID);<\/pre>\n","protected":false},"excerpt":{"rendered":"
This is all about priority queue problems with using different techniques for storing the data in a queue, the priority queue could be similar to a queue in a hospital ER ward where the people with the biggest of problems are treated first. I am finding all of the computer science course at Stanford really … Continue reading Priority queues<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[233],"class_list":["post-1076","post","type-post","status-publish","format-standard","hentry","category-c_and_cpp","tag-heap"],"_links":{"self":[{"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/posts\/1076","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/comments?post=1076"}],"version-history":[{"count":7,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/posts\/1076\/revisions"}],"predecessor-version":[{"id":1311,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/posts\/1076\/revisions\/1311"}],"wp:attachment":[{"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/media?parent=1076"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/categories?post=1076"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/tags?post=1076"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}