<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Mike Peritz on Medium]]></title>
        <description><![CDATA[Stories by Mike Peritz on Medium]]></description>
        <link>https://medium.com/@mike.peritz?source=rss-aa7f1eff87f9------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*PCg8Q5_durEtCYkxraYE0g.jpeg</url>
            <title>Stories by Mike Peritz on Medium</title>
            <link>https://medium.com/@mike.peritz?source=rss-aa7f1eff87f9------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 03:20:01 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@mike.peritz/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Practical Recursion: Implementing a File Tree View in React & Electron]]></title>
            <link>https://codeburst.io/practical-recursion-implementing-a-file-tree-view-in-react-electron-af62e7b46d26?source=rss-aa7f1eff87f9------2</link>
            <guid isPermaLink="false">https://medium.com/p/af62e7b46d26</guid>
            <category><![CDATA[recursion]]></category>
            <category><![CDATA[react]]></category>
            <category><![CDATA[electron]]></category>
            <category><![CDATA[redux]]></category>
            <category><![CDATA[nodejs]]></category>
            <dc:creator><![CDATA[Mike Peritz]]></dc:creator>
            <pubDate>Sat, 17 Jun 2017 01:24:03 GMT</pubDate>
            <atom:updated>2017-06-17T14:37:29.544Z</atom:updated>
            <content:encoded><![CDATA[<p>Recently, I published a react component to npm that renders a file tree React component in a native Electron application. It was a fun project, and pretty comprehensive, covering basic computer science techniques through advanced front-end frameworks, so I thought it would be a good topic to share.</p><p>This post assumes the reader has an in-depth knowledge of React, Redux, and JavaScript ES2015. Also, in examples, I have left out import statements to keep things simple.</p><h3>First, ….why?</h3><p>Good question. Why did I make this component? Recently I completed Fullstack Academy’s (<a href="http://www.fullstackacademy.com/">www.fullstackacademy.com</a>) 3 month immersive bootcamp. At the end of the program, students complete a comprehensive capstone project that showcases their skill as developers and usually includes a few new techniques that they picked up to make the project great. My group and I decided to make a desktop application that would allow developers to pair program together remotely from anywhere. You can find the <a href="http://pair-it.herokuapp.com/">deployed project here</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-LuPHDB9_HeemiY0kf5E2Q.png" /><figcaption>Pair.It landing page.</figcaption></figure><p>The app features peer to peer video, command line Git functionality for version control, and a live updating code editor. Alongside the code editor we wanted a responsive file tree view that would expand and contract when a user entered or closed a directory. I was responsible for implementing this, and realized it could be useful for others as an importable component. It also showed me a very practical use of recursion, and was a challenge to integrate into React, hence this post.</p><h3>Step 1: Creating the File Tree Object</h3><p>To create a representation of a file tree in JavaScript, the object literal came to mind as a great framework. So, how do we populate this object? Well, to start things off, we need a root directory, and access to the files and folders inside that directory. How do we get that? Enter Node’s fs library.</p><p>Because this component is implemented in a desktop Electron application, we have access to the file system and Node’s suite of methods that allow us to manipulate it. The first thing we need to do is get a list of all files and folders. <em>fs.readdir</em> gives us that. Because this method (and most other fs methods) are asynchronous, it would be nice if we could get these into a promise for more legible code flow and better error handling. Bluebird’s <em>promisifyAll</em> function allows us to create a promisified version of any set of asynchronous functions. So, our <em>readdir</em> function becomes <em>fs.readdirAsync</em>, and it gets used like so:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/382db3f6c4b3829d1e5f6c4e7439b7d0/href">https://medium.com/media/382db3f6c4b3829d1e5f6c4e7439b7d0/href</a></iframe><p>Easy. This returns a promise for an array of file/folder name strings.</p><p>So what’s next? For each file/folder we need to create an object with some useful information for our front end. For instance, it would be nice to know if what we’re dealing with is a file or a folder. How can we tell if a something is a file or a folder? Well, the <em>fs</em> library provides us a method that gives meta data about a file, given a file path. Its the <em>stat</em> method, and one of the bits of data it provides is a boolean, returned from an <em>isFile()</em> method invocation. It will return <em>true</em> for a file, and <em>false</em> for a directory. Let’s see it in action:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0d6c4e9678659470803f1e82e73cb0a7/href">https://medium.com/media/0d6c4e9678659470803f1e82e73cb0a7/href</a></iframe><p>OK, now for the hard part. We’re all set for files, but what about folders? Remember that folders can have folders inside them, and those folders can have folders inside them, and those folders can have….</p><p>We get it, Mike.</p><p>For each sub-directory, we need to do what we’re doing for the root directory: create an array of objects with important information about each file/folder for our front end. Recall the definition of recursion:</p><blockquote><strong>Recursion</strong> in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration).<a href="https://en.wikipedia.org/wiki/Recursion_(computer_science)#cite_note-1">[1]</a> The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.<a href="https://en.wikipedia.org/wiki/Recursion_(computer_science)#cite_note-2">[2]</a></blockquote><blockquote>[1] Graham, Ronald; Donald Knuth; Oren Patashnik (1990). <em>Concrete Mathematics</em>. Chapter 1: Recurrent Problems.</blockquote><blockquote>[2] Epp, Susanna (1995). <em>Discrete Mathematics with Applications</em> (2nd ed.). p. 427.</blockquote><blockquote>Credit: wikipedia.org</blockquote><p>That sounds like exactly what we need to do! So we’ll need to name our overall function, and then recursively call it when we encounter a folder.</p><p>Side note: recursive solutions typically depend on 2 cases: a recursive case, in which we recall our function, and a base case, in which we advance towards a terminating condition. This is what prevents us from exceeding our maximum call stack size. In our function, the base case is when we encounter a file, and the recursive case is when we encounter a folder.</p><p>I often find that its easier to solve recursive problems when you complete it in terms of the base case before adding in recursive calls. So let’s skip the recursive call for now, and come back to it later.</p><p>After we create our individual file object inside our mapping function, we need to return it. Then we need to take the array of promises we created and use <em>Promise.all</em> to resolve them in the order they came in:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7697137ecf9591b4bf51c266e3aba321/href">https://medium.com/media/7697137ecf9591b4bf51c266e3aba321/href</a></iframe><p>OK, now we know our function will return a promise for an array of resolved promises, so our recursive call is easy. We’ll just add that array to a <em>files</em> property on our file object:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/224990c44c1f89efa58fdfa189277393/href">https://medium.com/media/224990c44c1f89efa58fdfa189277393/href</a></iframe><h3>Step 2: Create the FileTree React Class</h3><p>Now that we can create an object literal representation of a file tree, we need to use it to render the file tree view. Let’s create a React class called FileTree, and give it a files property on its local state. The reason for this will become evident soon. We know that our generateFileTreeObject needs to be given a directory string, so let’s assume that our user will provide that string as a prop.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/64859a560492e6d73cbe6433629332fa/href">https://medium.com/media/64859a560492e6d73cbe6433629332fa/href</a></iframe><p>Now we’re cooking with gas. Let’s start the render process. This part is a little tricky. We’re going to want to use React’s componentDidMount hook to call our generateFileTreeObject function. We know this returns a promise for an array of file-objects, so let’s <em>.then</em> off of this promise and set <em>this.state</em> to the array. Always remember to handle errors with <em>.catch</em>!</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6a36825e15612178e295f0fab874d8c8/href">https://medium.com/media/6a36825e15612178e295f0fab874d8c8/href</a></iframe><p>Now for the actual render method. This part is tricky as well. How can we give our file tree a visual representation of depth, especially when we don’t know how many nested directories there may be? Does this sound like a familiar problem? It should, because it is similar to the one we tackled when creating our generateFileTreeObject function. We need to recursively create additional FileTree components for each directory we encounter. Let’s see what it looks like.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/800e3be5315b1287b5a5d6dab170cd0c/href">https://medium.com/media/800e3be5315b1287b5a5d6dab170cd0c/href</a></iframe><p>We’ve now rendered a full file tree view! Let’s be proud of our work! But how can we make this better? Well anyone who has used a modern text editor knows that the file tree should expand and contract when we click on directories. Let’s implement it!</p><h3>Step 3: Use React-Redux to Make the File Tree Dynamic</h3><p>Right now our file tree renders out all at once, with all levels showing. It would be great if it started out as a list of files/folders in the root directory, and expanded/contracted when we clicked on a folder. Redux and React-Redux’s connect function make this easy. We’ll start by putting an object on our store that will hold all of our “visible” directories. This will start out as an empty object since we want our tree to start out only displaying the root directory. Next we’ll define a constant and an action creator that will add key value pairs to our visibility store object. Each key will be the file’s path, and each value will be true or false. This action creator can serve both purposes of setting the keys to either true or false depending on their current value. Next, we’ll create our reducer which will execute this action, and import it into the store. Finally we can used our reducer to create our store. In a typical setting, we would separate these portions out into their own modules, but for the purposes of this post, we’ll keep them all together.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/74c15c3c472d94d647042cb074a95d9c/href">https://medium.com/media/74c15c3c472d94d647042cb074a95d9c/href</a></iframe><p>Now we need to use React-Redux’s connect function to pass this global state into our component. Thats easy too!</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6d5a22a16026fa59b8e0c0885318967a/href">https://medium.com/media/6d5a22a16026fa59b8e0c0885318967a/href</a></iframe><p>Finally, we need to change our component to conditionally render out each level, depending on its visibility as laid out in the Redux store. We’ll also need to change our jsx slightly to allow for a click handler which will dispatch our toggleVisibility action passed down in the connect function.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d39c0ae9e007ef458dd59efb7ee2ea34/href">https://medium.com/media/d39c0ae9e007ef458dd59efb7ee2ea34/href</a></iframe><p>And that’s it! There is a lot more functionality which could be implemented, such as a function that would fire when a file is clicked, icons to distinguish files from folders, styling, etc. You can find my completed implementation here: <a href="https://github.com/mperitz/react-filetree-electron">https://github.com/mperitz/react-filetree-electron</a>. It looks just like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*aq02q8OfHxthpRFkD_FAIg.png" /></figure><p>Please feel free to contribute to the project by making a pull request! Thanks for reading!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=af62e7b46d26" width="1" height="1" alt=""><hr><p><a href="https://codeburst.io/practical-recursion-implementing-a-file-tree-view-in-react-electron-af62e7b46d26">Practical Recursion: Implementing a File Tree View in React &amp; Electron</a> was originally published in <a href="https://codeburst.io/">codeburst</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Implementing a Complete Binary Heap in JavaScript: The Priority Queue]]></title>
            <link>https://codeburst.io/implementing-a-complete-binary-heap-in-javascript-the-priority-queue-7d85bd256ecf?source=rss-aa7f1eff87f9------2</link>
            <guid isPermaLink="false">https://medium.com/p/7d85bd256ecf</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[heap]]></category>
            <category><![CDATA[priority-queue]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[javascript]]></category>
            <dc:creator><![CDATA[Mike Peritz]]></dc:creator>
            <pubDate>Mon, 05 Jun 2017 21:26:30 GMT</pubDate>
            <atom:updated>2020-08-27T00:07:26.313Z</atom:updated>
            <content:encoded><![CDATA[<h3>What’s a heap?</h3><p>A heap is a tree-like data structure where each node must be ordered with respect to the value of its children. This ordering must persist throughout the entire heap. Put simply, a parent node’s value must always be greater (or less) than its children’s values. There are two types of heap: max heap and min heap. As you may have guessed, in a max heap, parent node values are greater than those of their children, whereas the opposite is true in a min heap.</p><h3>What’s a Binary Heap?</h3><p>Binary heaps are a specific implementation of a heap whereby each parent can have no more than two children. Additionally, a <em>complete </em>binary heap has every level filled, except for the bottom level. This level gets populated left to right.</p><h3>Why should I care?</h3><p>A heap is a useful and efficient way to store and look up data that must maintain order. The classic example is a priority queue abstract data type. A priority queue is a set of data where higher or lower valued data points bubble to the front of the queue and are therefore accessed first. We’re going to use that as our example in this post of how a heap can improve lookup efficiency. Please note: this example will make use of ES2015, so be sure to brush up on classes, arrow functions, and object destructuring before you read this!</p><h3>First, the naive solution.</h3><p>To understand how the binary heap will optimize our solution, it is important to see the naive solution. The naive solution to the priority queue is a linked-list data structure where each node has a “priority” key. Lets start by defining the node class:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/753764c51ee535c7057d840a26409b39/href">https://medium.com/media/753764c51ee535c7057d840a26409b39/href</a></iframe><p>Awesome. Now each node can have a value and a priority, and can point to the next node in our priority queue.</p><p>Now we can initialize our linked list. Lets call it PriorityQueue and give it a “first” property to represent the highest priority item in the queue.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f86c5b0c419bdb21cb9c99109d876cab/href">https://medium.com/media/f86c5b0c419bdb21cb9c99109d876cab/href</a></iframe><p>If we want to use our priority queue, we’re going to need to be able to insert values. Nodes with a higher <em>this.priority</em> will be inserted at earlier points in the linked list. To do this we must visit each node in the list until we find one with a lower <em>this.priority</em> than the new node we are inserting. Additionally, if we encounter a node(s) with the same priority, we must insert the new node after all nodes with matching priority. This can be accomplished iteratively with a pointer.</p><p>There are two edge cases to deal with:</p><ol><li>When the priority queue is empty, we set <em>this.first</em> to a new node with the passed in value and priority.</li><li>When the new node has a higher priority, we need to set its <em>.next</em> property to the current <em>this.first</em> node, and then reset <em>this.first</em> to be the new node.</li></ol><p>We can handle both edge cases if we just do the action described in #2 above in an if statement, and then we’ll handle all other cases in the else:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7fbbfa6026d3fa5da3e310a57d6391c6/href">https://medium.com/media/7fbbfa6026d3fa5da3e310a57d6391c6/href</a></iframe><p>Great! Now that we can add to the priority queue, we want to be able to remove elements as well. Since we know the highest priority node is always referenced as <em>this.first</em>, we just have to save a reference to its value, and then reset <em>this.first</em> to the next node in the queue:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2ea7504b1c9bf19b7f91da4ca7c79526/href">https://medium.com/media/2ea7504b1c9bf19b7f91da4ca7c79526/href</a></iframe><p>There you have it, a perfectly valid priority queue. But lets talk about efficiency. Because we potentially have to visit all items in the list, inserting values to the linked-list priority queue has O(<em>n</em>) time complexity, while removing them is constant time, or, O(<em>1</em>). That’s a very good lookup efficiency, but our insertion efficiency is mediocre at best. What if we could optimize our insertion to be O(<em>log n</em>)? As you may have guessed, we can do this using a binary heap.</p><h3>Optimized Solution: The Complete Binary Heap</h3><p>As stated above, a binary heap is a great way to implement the priority queue because it maintains the order (or <em>priority</em>) of its data, with the added bonus of a tree’s efficient insert time. Because complete binary heaps/trees handle insertion level-by-level, we can use JavaScript’s array object to hold our data, and use a <em>level-ordered</em> algorithm to dictate how each data point is stored. Typically, heaps have a lot of methods on their prototypes, but we are just going to implement insert and remove.</p><p>To understand this better, lets learn by example. Consider the simple complete binary heap below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/501/1*XSchy2OiWWwlkPNhhoKVBg.png" /></figure><p>Now lets walk through the level-ordered algorithm to see how this heap could be represented as a JavaScript array:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/61f4650c2760aabc3057d840e46831d0/href">https://medium.com/media/61f4650c2760aabc3057d840e46831d0/href</a></iframe><p>OK, now that we have a nice representation of the complete binary heap in JavaScript, lets implement our functionality. We can begin with insertion. Inserting any value must maintain the rules of our complete binary heap. Namely:</p><ol><li>The priority of the node that gets inserted cannot be greater than its parent.</li><li>Every level of the heap must be full, except the lowest level, which fills left to right.</li></ol><p>So, we begin by simply adding a new node to the end of our heap array. JavaScript arrays have a useful .push method which accomplishes this for us. We then need to adjust our heap array in order to obey the rules above. Since we know where every node’s parent is, this is a simple matter of checking the child node’s priority with its parent and swapping them if so. We continue to do this until the parent node has a lower priority than the child, or we run out of parent nodes, in which case the new node takes over the highest level of the heap. Lets see it in action:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7c7ed56e0ec30ebafbae1b749a632f25/href">https://medium.com/media/7c7ed56e0ec30ebafbae1b749a632f25/href</a></iframe><p>Because we are only visiting levels in the heap (as opposed to each node), our efficiency is at worst O(<em>number of levels</em>), which translates to O(<em>log n</em>), a drastic improvement over the linked-list solution efficiency of O(<em>n</em>).</p><p>Now lets implement removal. Due to the nature of a heap, our highest priority item is always at the top of the heap. So all we have to do is return the second item in <em>this.heap</em>, right? (Remember that the first element is <em>null</em>).</p><p>Sort of, but remember that now we’ve removed a node from our heap. It has to be replaced! We still have to obey the rules of the complete binary heap, so we can’t just swap elements willy-nilly. The first step is to pop off the last element of the heap, and set it to be our first element. This allows us to obey rule 2 above. Because there is a high likelihood that this element’s priority is lower than its children, we now have to start swapping it with its children until we satisfy rule 1 above. We do this by testing which child is higher, left or right. This is the reason we initialized <em>this.heap </em>with a zero index value of <em>null. </em>We have to start at index 1 order to multiply by 2 and find the first node’s children. If we started at index zero, we would never be able to find the first node’s children, because that calculation would always result in an index of zero.</p><p>Lets see one possible implementation of this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1c60b45eec043d145fe7c902c80d2587/href">https://medium.com/media/1c60b45eec043d145fe7c902c80d2587/href</a></iframe><p>Note the edge case taken care of in lines 2–6. This accounts for the fact that if we replace the first element in the heap with <em>this.heap.pop()</em>, we are replacing that element with itself! It also handles the case of an empty heap by returning null and replacing the zero index of the heap with a new <em>null</em> value.</p><p>So what is the efficiency of removal with this solution? Once again we may visit every level of the heap, meaning (just like insertion), we have a time complexity of O(<em>log n</em>). Isn’t this worse than our time complexity with the linked-list? Yup, but the gains we get in insertion will outweigh the loss we see in removal. Lets visualize this with a chart:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*EHKwJOq4iradT5hAr4nqSA.png" /><figcaption>Credit: Wolfram-Alpha</figcaption></figure><p>This plot shows the efficiency of each implementation if we were to add and then immediately remove between 1 and 50 elements from our priority queue. For the linked-list, the operation of adding and then immediately removing elements would be O(<em>n</em>) + O(<em>1</em>) which results in the blue line you see above. For the binary heap, the efficiency of this operation would be O(<em>log n</em>) + O(<em>log n</em>) which results in the red line above. The difference is clear. The sacrifice we make in our removal efficiency is totally worth it.</p><h3>Conclusion</h3><p>I hope this article has helped you understand more about heaps, and how they can improve time complexity. For more practice, try implementing additional methods like <em>peek</em>, a method that returns the first element in the priority queue without removing it. You could also try <em>heapify</em>, a method that will create a heap out of an array of elements.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7d85bd256ecf" width="1" height="1" alt=""><hr><p><a href="https://codeburst.io/implementing-a-complete-binary-heap-in-javascript-the-priority-queue-7d85bd256ecf">Implementing a Complete Binary Heap in JavaScript: The Priority Queue</a> was originally published in <a href="https://codeburst.io/">codeburst</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>